~EEE

TRANSACTIONS ON

INFORMATION

THEORY,

VOI..

36,

NO.

5,

SF.PTEMRER

1990

96

1

The Wavelet Transform, Time-Frequency

Localization and Signal Analysis

Abstract

--Two

different procedures are studied by which a frequency

analysis

of

a time-dependent signal can

be

effected, locally in time. The

first procedure is the short-time

or

windowed Fourier transform, the

second is the “wavelet transform,” in which high frequency components

are studied with sharper time resolution than low frequency compo-

nents. The similarities and the differences between these two methods

are discussed. For both schemes a detailed study is made

of

the

reconstruction method and its stability, as a function of the chosen

time-frequency density. Finally the notion

of

“time-frequency localiza-

tion” is made precise, within this framework, by two localization theo-

rems.

I.

INTRODUCTION

A.

The Windowed Fourier Transform and Coherent States

N SIGNAL ANALYSIS one often encounters the

so-

I

called short-time Fourier transform, or windowed

Fourier transform. This consists of multiplying the signal

f(t)

with a usually compactly supported window function

g,

centered around

0,

and of computing the Fourier

coefficients of the product

gf.

These coefficients give an

indication of the frequency content of the signal

f

in a

neighborhood of

t

=

0.

This procedure is then repeated

with translated versions

of

the window function (i.e.,

g(t)

is replaced by

g(t

+

to),

g(t

+2t,,);

.

e,

where

t,,

is a

suitably chosen time translation step). This results in a

collection of Fourier coefficients

c,,,(

f)

=

/r

dteimoll’g(

t

-

nt,,)

f

(t)

-m

(rn,nEZ).

(1.1)

Similar coefficients also occur in a transform first pro-

posed by Gabor [l] for data transmission. The original

proposal used a Gaussian function

g,

and parameters

wO,

to

such that

wo.t,,

=

2~. A Gaussian window function is,

of course, not compactly supported, but it has many other

qualities. One

of

these

is

that it is the function which is

optimally concentrated in both time and frequency, and

therefore well-suited for an analysis in which both time

and frequency localization are important. Gabor’s original

proposal, with

wO.to

=

2~,

leads to unstable reconstruc-

Manuscript received November

9,

1987; revised December

7,

1988.

This work was presented in part at the International Conference on

Mathematical Physics, Marseille, France, July 1986.

The author was with the Mathematics Department, University

of

Michigan, Ann Arbor, MI 48109-1003. She

is

now with AT&T Bell

Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974.

IEEE

Log

Number 9036002.

tion (see

[2],

[3]; we shall come back to this in Section

11-C-1). The Gabor functions have been used in many

different settings in signal analysis, either in discrete

lattices (with

~~.t~)

<

27-r

for stable reconstruction)

or

in

the continuous form described next.

In

many

of

these

applications their usefulness stems from their time-

frequency localization properties (see e.g., [41).

Whatever the choice for

g

(Gaussian, supported

on

an

interval, etc.), it

is

interesting to know to which extent the

coefficients

cm,(

f

1

of (1.1) define the function

f.

This is

one

of

the main issues of this paper.

The coefficients

cmn(

f)

in (1.1) can also be viewed as

inner products of the signal

f

to be analyzed with a

discrete lattice of coherent states. Let us clarify this

statement. By “coherent states” we understand here the

family of square integrable functions

g(p*q),

generated

from a single L2(R)-function

g,

by phase space transla-

tions

(p,q).

A “discrete lattice” of coherent states is a

discrete subset of the whole family obtained by restricting

the labels

(p,q)

to a regular rectangular lattice in phase

space. “Phase space,” a term we borrow here from physics,

stands for the two-dimensional time-frequency space,

considered as one geometric whole. More precisely,

g(p-9)(x)

is obtained from

g(x)

by a translation of

x

by

q,

and by a similar translation of the Fourier transform

d

by

p,

i.e.,

g(p,q)(

x)

=

e‘Pxg(

x

-

q).

(1.2)

Families of coherent states, as defined by (1.2), are used

in many different areas of theoretical physics. Their name

stems from their use in quantum optics (where the Gauss-

ian choice for

g

is favored,

g(x)

=

r-‘I4

exp(

-

x2/2)>

[5], [6],

but they have since spilled over to many other

fields. See e.g.,

[7]

for a review, including many general-

izations of the original concept.

In

quantum mechanics,

they are particularly useful in semiclassical arguments

because they make it possible to study quantum phenom-

ena in a phase-space setting. If the original function

g

is

centered around

(0,O)

in phase space, i.e., if the mean

value of position,

l&xlg(x)l*,

and of momentum,

/dkkli(k)l2,

are both zero, then the state

g(p.q’

will be

centered around

(p,

q),

i.e.,

0018-9448/90/0900-0961$01.00

01990 IEEE

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

962

IEEF TRANSACTIONS

ON

INFORMATION

THEORY, VOL.

36,

NO.

5,

SEPTEMBER

1990

Here

2

denotes the Fourier transform

of

g,

g(k)=

(2~>-’/~/dxe‘~~g(x). The inner products (g(p.4),

$1

will

therefore “measure” the phase space content of the func-

tion

$

around the phase space point

(p,q).

See e.g.,

[8,

Section V-A.] and [9] for

two

different methods

of

using

coherent states in a study of semiclassical approximations

to quantum mechanics.

A very important property of the coherent states is the

so-called “resolution of the identity.” It has been discov-

ered and rediscovered many times (see the earlier papers

in [7]). A discussion of its relevance for signal analysis can

be found in

[lo].

For the sake of completeness, we give its

(easy) proof in Appendix A. The “resolution of the iden-

tity” says that the map

@

from

L2(R)

into

L2(R2),

de-

fined by

@f(p,q)

=

(g(P~4),f), is an isometry (up to a

constant factor), i.e.,

Here, as in the remainder of this paper,

(f,

g) stands for

the L2-inner product of the functions

f

and g,

B.

Phase Space in Signal Analysis

The appearance of a phase space concept, such as the

coherent states, in signal analysis, is not altogether sur-

prising. As pointed out by

N.

G.

de Bruijn [ll], it is an

entirely natural concept in music. Let us consider a time-

dependent signal, which is a piece of music played (for

the sake of simplicity), by a single instrument. If we

disregard problems with high harmonics, with the “attack”

of the notes, etc. (this is a simple example!), the musical

score corresponding to the piece can be considered as a

satisfactory representation

of

the time-dependent acoustic

signal. A musical score indicates which notes have to be

played at consecutive time steps. Thus, it gives a fre-

quency analysis, locally in time, and is much closer to a

short-time Fourier transform or a coherent states analy-

sis, than to e.g., the Fourier transform, in which all track

of time-dependence is lost, or at least not explicitly recog-

nizable. The notation of a musical score, indicating time

horizontally, and frequency vertically, is really a phase

space notation. Phase space is thus seen to be a natural

concept in signal analysis. This is also illustrated by the

successful use, in signal analysis, of that other phase space

concept, the Wigner distribution, as in [12] or [131.

As long as the continuously labelled coherent states

g(Pxq) are used, we know, from (1.31, that knowing a signal

f

is equivalent to knowing the inner products (g(P34),f).

This need not be automatically true if one restricts the

labels

(

p,

4)

to the discrete sublattice

(mp,,,

nq,),

m, n

E

Z;

(note that this inner product is antilinear in the first

argument and linear in the second argument, following

the physicists’ convention), while

llfll

stands for the

L2-

norm of

f,

-.

~

-

..

Ilfll’=

(f,f)

=

/W(X)I2.

some conditions on

g,p,,q,

will be required. Let us

define the map

T

T:

L2(R)

-+

12(Z2)

Formula (1.3a) implies that

(

1.3b)

This means that a function

f

can be recovered com-

pletely, and easily, from the phase space “projections”

(g(p,q),f). Note that, since (1.3) holds for any g, one can

use this freedom to choose g optimally for the application

at hand. This freedom of choice was exploited in e.g.,

[8,

Section V-A]; it will also be important to us here.

If, instead of letting

(p,

q)

roam over all of phase space,

in a continuous fashion, we rather restrict ourselves to a

discrete sublattice of phase space, then we revert to (1.1).

That is, if we choose

po,

q,

>

0,

and we define

g,n(

.)

=

g(mP,l.n411)

=

eimptbxg(

x

-

nq,)

then clearly (with

x

interpreted as “time,”

po=

v,,

(Tf)m,n

=

(g,,,f)

=cm,(f).

(

1.4)

This map is the discrete analog of the “continuous” map

in Section I-A. For all the cases of interest to us, the

map

T

will be bounded.

To

have complete characteriza-

tion of a function

f

by its coefficients

c,,(f)

we shall

require that

T

be one-to-one. If the characterization of

f

by means

of

the

c,,(f)

is to be of any use for practical

purposes, one needs more than this, however. It is impor-

tant that the reconstruction of

f

from the coefficients

c,,(f)

(which is possible, in principle, if

T

is one-to-one)

be numerically stable: if the sequences

cmn(f),

c,,,(g) are

“close” for two given functions

f

and g, then we want

this to mean that

f

and g are “close” as well. More

concretely, we require that

Allfll’

5

I(gm,,,f)12

5

Bllfl12

(1.5)

m,n

40

=

to)

with A

>

0,

B

<

m,

and A,

B

independent

of

f.

This can

be rewritten, in operator language, as

c,,(f)

=

(gm,,f)

=

(g‘“”l13”“”’,f).

AnsT*TIBn.

(1.6)

This shows that the short-time Fourier transform can

indeed be viewed as the computation of inner products

with a discrete lattice of coherent states.

Here the inequality

TI

I

T2,

where

TI, T2

are symmetric

operators on

L2(R),

stands for

(f,

T,

f

)

I

(f,

T2f

)

for all

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

~

963

f

E

L2(R).

A

set

of

vectors

(4j;

j

E

J)

in a Hilbert space

2

for which the sums

CjE,l(~j,f)12

yield upper and lower

bounds for the norms

llf1I2,

as in

(1.51,

is also called a

frame.

The concept “frame” was introduced by Duffin

and Schaeffer

1141

in the context of nonharmonic Fourier

analysis; see also

[15].

We shall thus require that the

(g,,;

m,n

E

7)

constitute a frame; we shall give the name

frame bounds

to the constants

A,

B.

In a previous paper

[161

particular functions

g

were

constructed, for given

po,

go

>

0

(with

po’qo

<

27r)

such

that the corresponding

g,,

constitute a frame. For this

special construction, the frame bounds

A,

B

are known

explicitly in terms of

g,

and explicit inversion formulas for

T

can be given. In a particular case

of

this construction

one even finds that the inequalities in

(1.51,

(1.6)

becomes

equalities, i.e.,

A

=

B.

Whenever

A

=

B

the frame is

called a

tight frame.

The inversion

cm,(

f)

+

f

then be-

comes trivial; since

T*T

=

An,

one has

f=A-‘T*Tf=A-‘

gm,(gm,,f)

m,n

where the sum converges strongly, i.e.,

Remark:

Note that frames, even tight frames, are not

bases in general, in spite

of

the resemblance between the

reconstruction formula for a tight frame and the standard

expansion with respect to an orthonormal basis. In gen-

eral, a frame contains “too many” vectors. An example in

the finite-dimensional space

C2

is given by

U,

=

e,,

u2

=

-

1/2e,

-k

6/2e2,

u3

=

-

1/2e,

-

6/2e2,

where

e,

=

(1,O)

and

e2

=

(0,l)

constitute the standard basis for

C2.

One easily checks that, for all

U

E

C2,

32

I

(U/,

v)

l2

=

-Ilvll

3

2

/=I

so

that the

(U/;/

=

1,2,3)

constitute a tight frame, with

inversion formula

The

{U,;

I

=

1,2,3)

do not constitute a basis because they

are not linearly independent. In the infinite-dimensional

frames we shall consider in this paper any finite number

of

vectors will be linearly independent in general, but

there will still be “too many” vectors in the sense that any

of them lies in the closed linear span of all the others. If

the vectors constituting a tight frame are normalized, then

the frame constant

A

=

B

indicates the “rate of redun-

dancy” of the frame; if

A=

B=

1

then the frame is

automatically an orthonormal basis.

While the constructions in

[

161

lead to satisfactory and

easy inversion formulas for

T,

they have the drawback

that the function

g

cannot be chosen freely, but has to be

of the very particular type constructed in

[161.

For some

applications however, the window function

g

might be

imposed

a

priori,

and not be of this particular type.

In

that case it is of interest to find ranges for the parameters

po,qo

such that the

g,,,

associated with the triplet

g,po,qo,

constitute a frame.

As

we shall see next,

snug

frames,

which are close to tight frames, i.e., for which the

ratio

B/A

is close to

1,

are particularly interesting,

because they lead to easy inversion formulas with rapid

convergence properties. It is therefore important to have

good estimates for the frame bounds

A

and

B.

One of

the questions we shall address in this paper is therefore

the following: given

g,

1)

find a range

R

such that for

(po,

qo)

E

R

the associ-

2)

for

(po,qO)~

R,

compute estimates for the frame

Once good estimates for the frame bounds

A, B

are

obtained, one can construct a dual function

g

(depending

on

po,qo

as well as on

g;

see Section

II-A

next) which

leads to the easy reconstruction formula

ated

g,,

are a frame, and

bounds

A,

B.

f(x)

=

C

(gmn7f)elmP‘1xg(~--nq,,).

m,n

The function

2

is essentially a multiple of

g,

with correc-

tion terms

of

the order of

B/A

-

1;

the closer

B/A

is to

1,

the faster the series for

2

converges. Obtaining good

frame bounds is important even

if

different reconstruc-

tion procedures are considered, or

if

only characterization

of

f

by means

of

the

cm,(f>=

(g,,,f)

and not full

reconstruction (after e.g., transmission) is the main goal,

since

any

stable reconstruction or characterization proce-

dure can exist only if the

g,,

constitute a frame.

All of these concern expansions with respect to coher-

ent states constructed according to

(1.2).

We shall also

discuss a different type of expansion, the so-called “wave-

let expansion”

[17]

,

[18],

which corresponds to coherent

states of a different type.

D. Wavelets

-

A

Different Kind

of

Coherent States

The coherent states

g(p.4)

all have the same envelope

function

g,

which is translated by the amount

q,

and

“filled in” with oscillations with frequency

p

(see Fig. la).

They typically have all the same width in time and in

frequency. “Wavelets” are similar to the

g(ps4)

in that

they also constitute a family of functions, derived from

one single function, and indexed by

two

labels, one for

position and one for frequency. More explicitly,

where

h

is a square integrable function such that

and where

a,

b

E

R,

a

#

0.

Note that

if

h

has some decay

at infinity, then

(1.7)

is equivalent to the requirement

/dxh(x)=O.

The parameter

b

in the

h(“Xb)

gives the

position

of

the wavelet, while the dilation parameter

a

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

964

,-‘

/

‘,

hl,-6

li

\\

i/

‘\

\

I

\

IEEE

TRANSACTIONS

ON

INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

Re

943

\

1

I1

/I

//

-2,30

I/

I1

II

/I

I1

/I

I/

I1

/I

(b)

(a) Typical choice for the window function

g= g,,,

and typical

gm,,.

In this case g(x)=P-’/4exp(-x2/2),

p,

=

T,

q,

=

1;

figure shows

Re

g4&x)

=

T-’/~

cos(4~x)exp[

-(x

-3)2/2]. (b) Typical choice for basic wavelet

h

=

h,,

and a few typical

hm,,.

In this case

h(x)

=

2/fi~-’/~(l- x2)exp(- x2/2),

a,

=

2,

bo

=

1.

Fig.

1.

governs its frequency. For

la1

-=x

1, the wavelet

h(‘*’)

is a

very

highly concentrated “shrunken” version of

h,

with

frequency content mostly in the high frequency range.

Conversely, for

lul

>>

1,

the wavelet

h(‘,’)

is very much

spread out and has mostly low frequencies (see Fig. l(b)).

As a result of this construction, wavelets will be a better

tool than the “canonical” coherent states

g(p,q)

in situa-

tions where better time-resolution at high frequencies

than at low frequencies is desirable.

There exists a resolution of the identity for wavelets as

well as for the canonical coherent sates. One finds, for all

fl,

f2

E

L2(m

See Appendix A. Again, this implies that a function

f

can

be recovered easily from the inner products

(

A(‘,’),

f

),

since

The similarities between the

g(p,q)

associated with the

short-time Fourier transform and the wavelets

h(‘,’)

are

no accident: both families are special cases of “coherent

states associated with a Lie-group,’’ in the first case the

Weyl-Heisenberg group, in the second case the

‘‘U

+

b”-

group or affine group. Wavelets are therefore also called

“affine coherent states.” They were first introduced, un-

der this name, in [19]. They are of great interest for their

own sake, and have led to interesting applications in

quantum mechanics (see, e.g., [20], [211). They are also

related to the use of dilation and translation techniques in

harmonic analysis, which have turned out to be very

powerful tools. It is likely that these techniques, and

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES:

THE WAVELET

TRANSFORM,

TIME-FREQUENCY

LOCALIZATION

AND SIGNAL

ANALYSIS

965

affine coherent states, will find interesting applications in

quantum mechanics problems (see e.g.,

[22]).

We shall not

go into these aspects here. Note that the “resolutions of

the identity” (1.3) and (1.8) can be used as starting points

for the construction of time-frequency localization or

fil-

ter operators

[23],

[24].

E.

Discrete Lattices of Wavelets -The Wavelet Transform

In analogy to the lattice of coherent states associated

with the short-time Fourier transform, which can be

viewed as a discrete subset of the continuously labeled

g(p99),

we shall also consider discrete lattices of wavelets.

We choose to discretize the dilation parameter

a

by

taking powers of a fixed dilation step

a,

>

1,

a

=

a;;l

with

m

E

Z.

For different values of

m

the wavelets will be

more or less concentrated, and we adapt the discretized

translation steps to the width

of

the wavelet by choosing

b

=

nb,,ay,

with

n

E

Z.

This leads to

h

mn

(x)

=

h(‘C,‘‘b~~‘~)(

x)

=

a;m/2h(

aitnx

-

nb,).

(1.9)

As we shall see, it is also important for the discrete case

to have

l&h(x)

=

0.

The “discrete wavelet transform” is the analog

of

the

map defined by

(1.4)

for the Weyl-Heisenberg case.’

Again one can investigate, as in the Weyl-Heisenberg

case, whether the

h,,

and the associated wavelet trans-

form lead to a “discrete approximation” of the resolution

of the identity

(l.B),

i.e., whether a family

of

wavelets

h,,

constitutes a frame. As was shown in [16], it is possible,

given

ao,bo,

to construct explicit functions

h

such that

the associated

h,,

constitute a frame, or even, in particu-

lar cases, a tight frame. These functions

h

are, as in the

Weyl-Heisenberg case,

o,f

a

very

particular type. Typicall?

their Fourier transform

h

has a compact support; since

h

may be chosen in

C”,

the function

h

may have arbitrarily

fast decay, or

Ih(x)

I

ck(1+

Ixl)-k

(1

.lo)

with

ck

<03

for all

k

E

N.

In practice, however, the con-

stants

ck

turn out to be fairly large for functions

h

of the

type constructed in [16]. This means that while

h

satisfies

(1.101, its graph is very spread out (see [161); typically the

distance between the maximum

x,

of

h

and the point

x

defined by

sup{lh(y)I;

y

2

x)

=

10-*1h(x,)l

will be an or-

der

of

magnitude larger than

b,,

the translation step

parameter. For practical purposes, it is desirable to use

functions

h

that are more concentrated than this, such as

e.g.,

h(x)

=

(1

-

x2)e-x2/2.

We shall therefore address the

same questions as the Weyl-Heisenberg case, i.e., for

given

h

:

1) find a range

R

for the parameters such that for

(a,,

bo)

E

R

the associated

h,,

constitute a frame;

and

2)

for

(a,,b,)

E

R,

compute estimates on the frame

bounds

A,

B.

‘To

distinguish the

g,,

from

the wavelets

h,,,,

we

shall call the

g,,

“Weyl-Heisenberg” coherent states, after the group with which

they

are

associated (see Section

I-D).

The wavelet transform can be used, like the short-time

Fourier transform, for signal analysis purposes. As in the

short-time Fourier transform the

two

integer indices,

m

and

n,

control respectively, the frequency range and the

time translation steps. There are however some signifi-

cant differences between the two transforms. Some of

these differences may well make the less widely used

wavelet transform a better tool for the analysis of some

types of signals (e.g., acoustic signals, such as music or

speech) than the short-time Fourier transform. Let us

digress a little on a qualitative discussion of these differ-

ences.

F, Qualitative Comparison of the Short-Time Fourier

Transform and the Wauelet Transfom

To illustrate this comparison we give graphs of typical

g,,

and

h,,

in Fig. 1, and of the associated phase space

lattices in Fig.

2.

More specifically, we represent each

g,,

or

h,,

by the point in phase space around which that

function is mostly concentrated. In the Weyl-Heisenberg

case, assuming that

/&

lg(x)I2

=

1

and

/&xIg(x)l2

=

0

=

/dkklg^(k)12,

the lattice points are given by

In the affine case we again associate to every

h,,

the

space localization point

/&xlh,,(x)12

=

nb,a,”

(assuming

that

/&lh(x)I2

=

1

and

/dxxlh(x)12

=

0).

Since the func-

tion

Ifit

and consequently all the

I(~,,)l

is even in many

applications, the choice

/dkkl(h,,)

(k)12

is not appropri-

ate for the frequency localization, since thisA integral is

zero. This is due to the fact that the

(h,,)

have

two

peaks, one for positive and one for negative frequencies.

We therefore represent the frequency content of

h,,

by

two

points, namely

The two lattice points corresponding to the positive and

negative frequency localizations of

h,,

are thus

(nb,a;;,

airn@

5

1

where

w+

=

+k

<,dkklh(k)12.

In Fig.

l(a)

a few typi-

cal Weyl-Heisenberg coherent states were given, in Fig.

l(b) some typical wavelets. Fig.

1

shows one very basic

difference between the two approaches; while the size of

the support of the

g,,

is fixed, the support of the

h,,

is

essentially proportional to

ay.

As

a result, high frequency

h,,,

which correspond to

rn

<<

0,

are very much concen-

trated. This means, of course, that the time-translation

step (if

x

is interpreted as “time”) has

to

be smaller for

high-frequency

h,,,

as shown by the phase space lattice

in Fig. 2(b). It also means, however, that the wavelet

transform will be able to “zoom in” on singularities, using

more and more concentrated

h,,

corresponding to higher

and higher frequencies.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

966

IEEE

TRANSACTIONS ON INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

.

0

.

k

0

. . . .

(b

0

.

. .

4,

. . . .

Ik

......

.ao.k.l(-??

..........

(-CO)

(-4,2)

(0,O)

(0,O

(0,2)

I

....................

(b)

t

corresponds to a value for

m

of approximately

67rf;

‘pi

’.

In practice however, since

T

B

to,

much higher values of

m will be needed to reproduce, by means of the

g,,

sketched in Fig. l(a> (and which all have width

T),

a

function

f

which is nonzero only in the interval

[O,t,].

This is not the case

if

wavelets are used. The high

frequency wavelets have very small support,

so

that the

above problem (having to bring in much higher frequen-

cies than intuitively needed) does not occur. Moreover,

even for the high frequencies corresponding to

f,

which

correspond in the wavelet transform to very negative

values of

m

and a very small time translation step (see

Fig. 2(b)), only a few

of

the many time-steps necessary to

cover

[0,

TI

would be needed, namely only those corre-

sponding

to

[0,

to].

This is what is meant by the “zooming

in” property

of

the wavelets. For this kind of problem,

wavelets thus provide a more efficient way (needing fewer

coefficients) of representing the signal.

I

Fig.

3.

One component of attack of note (see text).

We

take, as model,

Fig.

2.

(a) Phase space lattice corresponding to short-time Fourier

transform (see text).

(b)

Phase space lattice corresponding to wavelet

transform (see text). Constant

k,

is given

by

k,

=

/,”dkk-l16(k)12;

we

have assumed

h

to be even, and we have chosen

a,

=

2.

sin

(6af

/

tn)

,

OSt<t”

0

ts0,

or

f

t

t,,.

Lowest frequency of interest is 2aT-I; typically

to

T.

Let us illustrate this by the following simple example,

taken from a grossly simplified problem in the synthesis of

music. Typically one needs to be able to handle relatively

low frequencies corresponding to the lowest notes and

very high frequencies corresponding to high harmonics.

Suppose one wants to be able to represent tones with

frequency of the order of

27r/T.

Suppose also that one

wants to be able to render faithfully the “attack” of notes.

This “attack” consists

of

very high harmonics at the start

of the note which die out very quickly, typically in a time

to

T.

We have represented one component of such an

“attack” very schematically in Fig.

3.

Intuitively, the func-

tion

f(t)

in Fig.

3

seems to correspond to a signal with

“frequency”

2.sr3/tO

during the time interval

[O,

to],

while

its amplitude on

[[,,,TI

is zero. Let us compare the

performances of discrete Weyl-Heisenberg coherent

states and

of

wavelets for this problem. In the first case,

the support of

g,

and hence that of all the

g,,,

needs to

have a width

of

at least

T.

The high frequency

6r/to

This example is

so

much simplified that it is rather

unrealistic. The “zooming in” faculty of the wavelets,

illustrated by this example, does however play an impor-

tant role in more realistic applications; it makes the

wavelets a useful tool in the areas of signal analysis such

as seismic analysis

[25]

and music synthesis

[26].

This

same property also makes the wavelets a choice tool for

the detection

of

singularities

[27], [28],

which is of great

interest to the analysis

of

vision

[29], [381,

[40],

and for the

study of fractals

[67].

As

a final remark we note that the wavelet transform,

unlike the short-time Fourier transform, treats frequency

in a logarithmic way (as clearly shown by Fig.

2),

which is

similar to our acoustic perception. This corresponds to

constant

Q

as opposed to constant bandwidth filters. This

is another argument for the use of wavelets for the

analysis and/or synthesis of acoustic signals.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECIIIES:

THE

WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SlGNAI. ANAL-YSIS

~

967

G.

Short Historical Reiiew

of

the Wucelet

Transform

-Orthonormal Buses

of

Wurielets

As was already pointed out at the end

of

Section

I-E.

the use

of

functions

h(’,’)

generated from a single initial

function

h

by means

of

dilations and translations is not

new in either mathematics or physics, although their use

is not

so

widespread as the Weyl-Heisenberg coherent

states

g(p-y’

described in Section

I-A.

The use of the

h(‘*’)

for signal analysis purposes, analogous to the use of

the short-time Fourier transform,

is

much more recent,

however. As a tool for signal analysis, the wavelet trans-

form was first proposed by the geophysicist

J.

Morlet in

view of applications for the analysis

of

seismic data

[

171,

[25].

J.

Morlet’s original name for the wavelets was “wave-

lets of constant shape”, to contrast them with the analyz-

ing functions in the short-time Fourier transform, which

do not have a constant shape (see Fig.

1).

The numerical

success of

J.

Morlet’s method prompted A. Grossmann to

make a more detailed study of the wavelet transform; this

resulted in the recognition that the wavelets

h(a*h)

corre-

sponded to a square integrable representation of the

ax +

b-group. The resolution

of

the identity

(1.8)

and

associated interpolation techniques were then proposed

(and implemented) for reconstruction schemes. This work

was presented in a series of papers

[17], [18], [30],

in

which the original longer name was shortened to “wave-

let.” These papers were concerned with the map associat-

ing to a function

f

E

L2(W

the function

@f(u,b)=

(h(“,’),f),

where

a,

b ran continuously over

R*

X

R.

(Here

R*

=

R\{O}.)

For closer comparison with the numerical

situation,

it

is necessary to limit oneself to the discrete

sublattices described in Section I-F. Again

it

was

A. Grossmann who first realized the importance of

the “frame” concept in this connection. It was around

this time that

I

first became involved in the subject.

Around the same time

Y.

Meyer, having learned about

A. Grossmann’s and

J.

Morlet’s results, pointed out to

them that there was a connection between their signal

analysis methods and existing, powerful techniques in the

mathematical study of singular integral operators. All this

resulted in our first construction of a special type of

frames

[16].

It also was the start of a cross-fertilization

between the signal analysis applications and the purely

mathematical aspects

of

techniques based on dilations

and translations. The wavelet frames constructed in

[161

are based on functions

h

with compactly supported and

C”

Fourier transform. A similar construction can be

made for Weyl-Heisenberg coherent states

[161.

In that

case, due to the Balian-Low theorem (see Section

11-C-l),

there is a tradeoff between redundancy of the frame and

smoothness of the frame functions:

if

one requires the

g,,,

to constitute a basis (i.e., no redundancy), then either

xg(x)

or

kg(k)

is not square integrable. For the

Weyl-Heisenberg case one is thus forced to consider

frames rather than bases

if

the phase space localization

properties of

g

are important. It seemed natural to as-

sume that the same would be true for the affine case, and

[16]

was written under that implicit assumption (although

it is never explicitly stated). Shortly after

[16]

was written,

however,

Y.

Meyer constructed an orthonormal basis, for

Lz(R),

of wavelets

h,,,,

based on a function

h,

with

compactly supported and

C”

Fourier transform

h

[311.

This quite amazing basis turned out to be an uncondi-

tional basis for all LP-spaces,

1

<

p

<CO,

all the Sobolev

spaces, etc,

[31].

A

basis

{e,},,,

in a Banach space

E

is

called “unconditional”

if

the convergence of

C,Alel

de-

pends only on the

IA,[,

and is therefore independent of,

e.g., the order in which the terms are summed. For a

normalized basis

{e,},,, (Ile,ll

=

1

for all

I)

in a Hilbert

space

2,

this is equivalent to requiring that there exist

A

>

0,

B

<m

so

that, for all

v

E

2,

AMI’

I

1

(e,,v>

1’

I

BII~II’.

IC

J

In a Hilbert space a normalized basis is thus an uncondi-

tional basis

if

and only if it is also a frame. Such bases are

also called Riesz bases. Every orthonormal basis is auto-

matically a Riesz basis;

if

(+,,),tN

is an orthonormal

basis, then

e,

=

(1

+

n2)-’/2(n+,

+

+,)

is an example

of

a

basis of normalized vectors that is

not

a Riesz basis. The

Meyer basis was generalized to more than one dimension

by P. G. Lemarit and

Y.

Meyer

[32].

Even though the

function

h

in

Y.

Meyer’s basis has fast decay in the

mathematical sense (it decays faster than any inverse

polynomial), the constants involved are very large,

so

that

it is not

very

well localized in practice. This limits its

usefulness for signal analysis. If one is willing to accept

functions

h

with less regularity

(,Ck

instead of

C”)

and to

forego the compact support of

h,

then bases with better

localization can be used. G. Battle

[33]

and

P.

G. LemariC

[34]

independently, using very different approaches, con-

structed orthonormal bases with exponential decay. Ph.

Tchamitchian

[35]

constructed bases of compactly sup-

ported wavelets, which are however nonorthogonal.

A major breakthrough in the understanding of or-

thonormal wavelet bases came with the concept of mul-

tiresolution analysis, developed by

S.

Mallat and

Y.

Meyer

[36], [371.

A multiresolution analysis consists in breaking

up

L2(R)

into a ladder of spaces

<,

where

V-,

-+

L2(R)

for

m

-03.

The orthonormal projec-

tions onto the

V,

correspond to approximations with

“resolution”

2”;

a typical (but too simple to be practical)

example is

...

cv2cVlcV~cV~,cV~,c

*..

V,

=

{f

E

L*(R);

f

is constant on every interval

[121,

(I

+

1)2~),

I

E

z}.

The

V,

are all obtained from

V,

by the appropriate

dilation,

and

V,,

is generated by the integer translates

&,(x)=

4(x

-

n)

of one single function

4.

(In this example,

4(x)

=

1

for

0

5

x

<

1,

4(x)

=

0

otherwise). Then there

f(

.>

E

v,

-

f(2’x)

E

V,,

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

968

IEEE

TRANSACTIONS ON INFORMATION

TIIEORY,

VOI..

36.

NO.

5,

SEPTEMBER

1990

exists a function

JI

such that the JI,,(x)=2-”*JI(2-’x-n),

j

fixed, are an orthonormal basis of the orthogonal

complement

W,

of

5

in

V,-l.

In other words, the inner

products

{(JI,,,f);

n

E

Z)

contain exactly all the informa-

tion that is present in the approximation to

f

at level

j

-

l

(with resolution 2’-‘) but which is lacking in the next

coarser level

j

(resolution

29.

Because of the “ladder

property” of the

V,

it follows that the whole collection

(JI,,;

j,n

E

Z)

is an orthonormal basis of wavelets for

L2(R>.

Readers who would like to learn more about

multiresolution analysis should consult

[361, [371,

or

[381,

where explicit recipes are given for the construction of

wavelet bases, together with examples. Wavelet decompo-

sitions using multiresolution analysis have been imple-

mented in vision analysis

[38], [401.

A short review is also

included in

[39].

Note that there is a connection between

orthonormal wavelet bases and quadrature mirror filters,

used in subband coding

[39], [401.

Incidentally, the discovery of multiresolution analysis is

another instance in which signal analysis applications

provided the first intuition leading to the mathematical

construction. Existing, more rudimentary techniques in

vision analysis inspired

S.

Mallat to view orthonormal

wavelet bases as a more refined tool for multiresolution

approximations, which led to

[361, [37].

S.

Mallat has

implemented these ideas, using the Battle-LemariC bases,

into an algorithm for decomposition and reconstruction of

images

[29], [381.

Finally, in February

1987,

using Mallat’s

algorithm as inspiration, I succeeded in constructing or-

thonormal bases of wavelets with compact support, which

are discussed elsewhere

[39].

These different families of orthonormal wavelet bases

have created quite a stir among mathematicians. Apart

from applications to signal analysis, they should be useful

in physics also. A first application, to quantum field

theory, can be found in

[41].

All these orthonormal bases

are, however, rather spread out numerically, if one wants

h

to be reasonably regular

(h

E

Ck,

with k large enough).

If one

is

willing

to

give up the requirement of a basis

and to settle for a frame (giving up the linear indepen-

dence-see the remark in Section 1-0, then much better

localized

C”

h

can be chosen. This makes frames more

interesting than orthonormal bases for certain wavelet

applications in signal analysis. Another reason is that, as

will be shown later, for a given desired reconstruction

precision, frames allow one to calculate the wavelet coef-

ficients with less precision than would be needed in the

orthonormal case; the number of coefficients calculated

is, of course, higher. This may be useful in some numeri-

cal applications. The present paper addresses “frame”

questions. We shall formulate criteria under which the

h,,

constitute a frame, and then derive some properties

of

these frames. Since similar techniques can be used for

Weyl-Heisenberg coherent states, we address the same

questions for that case as well. The basic results of this

paper were reported, in an abridged version, at two

mathematics conferences, in March

1986

[42] and July

1986 [43],

respectively.

H.

Organization

of

the

Paper

In Section

I1

we study “frame questions.” We start with

some generalities concerning frames in Hilbert spaces.

We review the construction of

[16],

leading to tight frames.

For more general choices of the initial function

g

or

h,

we answer the questions

1)

and

2)

asked previously (suffi-

cient condition for frame, estimates for the frame con-

stants

A

and

B),

both for the Weyl-Heisenberg and for

the wavelet case. We discuss whether certain ranges for

po,

4,)

or

a,,,

6,)

are

a

priori excluded, and we give inequal-

ities linking

A,

B,

g,

or

h

and po,qO or

aO,bO.

We give

many examples, and numerical tables of frame constants

for these examples. For particular choices of

g

or

h,

our

results can be translated into estimates on entire func-

tions

[44].

A special case of this kind of estimate was

already given in

[451.

Since numerically one is also inter-

ested in convergence in other topologies than only

L2,

we

address the question of convergence in other spaces as

well. To improve the readability

of

the paper, we have

relegated many of the technical proofs to appendices.

In Section 111 we show how to use these frames for

phase space localization. Concretely this means the fol-

lowing. Suppose that a signal

f

is mostly concentrate$ in

[-

T,T]

in time, and that its Fourier transform

f

is

concentrated mostly between the frequencies

fl,

and

Oz.

This means that in phase space,

f

is mostly concentrated

on

[-T,T]X([-LR2,

-flI]U[LRI,f12]).

One would then

expect that only those phase space lattice points, in Fig.

2,

lying within this box (plus those lying

very

close to it)

would suffice to approximately reconstruct

f.

It turns out

that this intuition is essentially right. Note that such a

“box” contains only a finite number of points. We also

show how the “over-sampling’’ inherent to working with

frames permits, for fixed desired precision on the recon-

struction of

f,

to compute the coefficients

c,,(f)

with

less precision than would be needed in the orthonormal

case.

I.

Some Remarks

A

first remark we want to make is that while we shall

stick, throughout the paper, to one dimension (i.e., a

two-dimensional phase space), it is possible to generalize

the results to more than one dimension. For the

Weyl-Heisenberg case this is trivially true. For the wavelet

case two possibilities exist. In the first case dilations and

translations are used, independently in the

n

dimensions,

and then again the extension is trivial. In the second case

one uses n-dimensional translations, but only one dilation

parameter, which acts simultaneously on all dimensions.

In this case several (a finite number)

hi

have to be

introduced. This construction is then similar to the gener-

alization in

[32]

of

Y.

Meyer’s basis to

II

dimensions: in

that case

2“

-

1

different functions

hi

are used.

A

second remark is that we, have restricted ourselves

here to regularly spaced lattices, in the Weyl-Heisenberg

(WH) case as well as the wavelet case. While it is possible

to relax this regularity somewhat (we can also handle the

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

969

WH case

if

one of the two variables,

p

or

q,

is not

regularly spaced, as long as the other is; likewise, in the

wavelet case, we can handle dilations that are more

irregular than the geometric sequence

ay),

the methods

presented here are essentially unable to cope with distri-

butions of phase space points that would have the same

density (and this probably suffices to define frames, as in

nonharmonic Fourier analysis

[

1511, but which would not

be given by lattices. Using different methods, one can

indeed show that less regular phase space point distribu-

tions with a sufficiently high density do indeed lead to

frames. For very special choices of

g

or

h

for which the

“frame questions” can be formulated as properties of

entire function spaces, that was proved in [451, [47]. Using

the full power of the underlying group structure,

Feichtinger and Grochenig [48] proved the same result for

much more general functions

g

or

h

(essentially, they

only require that

g

or

h

is reasonably “nice”), without

recourse to entire function spaces. The results in [46]-[48]

are, however, more qualitative than quantitative in that

they establish that certain discrete families of coherent

states constitute frames without caring too much about

the values

of

the frame constants. Moreover, the phase

space densities of the discrete families considered in

[46]-[48] seems

to

be considerably higher than in our

examples.

11. FRAMES

AND

FRAME BOUNDS

A.

Generalities Concerning Frames

We start by reviewing some general properties of frames

Suppose that the

(4,;

I

EJ)

constitute a frame in the

Hilbert space

A?,

i.e., there exist

A

>

0,

B

<m

such that,

for all

f

E

2,

[141,

[151.

AlIf11’1

I(4,,f)I2

I

Bllfll’. (2.1.1)

I6

J

Define

T:

A?-+I’(J)

by

(Tf),=

(4/,f).

Here

I’(J)

stands for the space of square summable complex se-

quences indexed by

J.

The operator

T

is clearly bounded,

llTf

11

I

B1’’1l

f

11.

We shall call

T

the “frame operator”

associated with the frame

(41)lEJ.

Its adjoint operator

T*

maps

I2(J)

onto

2;

it is defined by

T*c

=

CIEJc,4/,

where

c

=(c/)/~~

E

12(J).

The frame inequalities (2.1.1)

can be rewritten as

AllsT*TIBll.

Since the symmetric operator

T*T

is bounded below by a

strictly positive constant, it is invertible, with a bounded

inverse. This inverse satisfies

B-’l

I

(T*T)-’s

A-lll.

(2.1.2)

Define

6,

=

(T*T)-’+,.

Then the family

($,),,,

consti-

tutes another frame. More precisely, we have

Proposition

2.

I:

1) The family

($l)ltJ,

with

$,

=

(T*T)-’4,,

constitutes

a frame with bounds

B-’

and A-’.

2) The associated frame operator

f

is given by

f=

f*f

=

(T*T)-’

f*T

=

1

=

T*f

T(T

*T)-’

and satisfies

(2.1.3)

where

fT*

=

Tf*

is the orthogonal projection oper-

ator, in

/’(I),

onto the range of

T.

Proofi

For any

f

E

2,

we have

<&f>

=(

(T*T)-%,f)

=(

4/,(T*T)-’f)

*

Hence

ci($,,f)i’=

IIT(T*T)-’~II’

=(

f,(T*T)-’f).

I

=

(

(T*T)

-‘~,T*T(T*T)

-If)

It then follows from (2.1.2) that the

<$,),,,

consti-

tute a frame, with frame _bounds

B-’

and A-’.

By the definition of the

4,

we have

(ffh

=

<$,,f>

=

((T*T)-’4/?f)

=

($/,(T*T)-’f)

=

(T(T*T)-’f),,

hence

T-

=

T(T*T)-’.

It follows that

f*f

=

(T*T)-’T*T(T*T)-’

=

(T*T)-’

F*T

=

(T*T)-’T*T

=

n,

and

T*f

=

T*T(T*T)-’

=

1.

Finally

fT*

=

T(T*T)-IT*

=

Tf*;

it remains to

prove that this is the orthogonal projection operator

P

onto the range

of

T.

Since

T*c=O

for any

c

orthogonal to the range of

T,

it suffices to prove

that

T(T*T)-’T*c

=

c

for

c

in the range of

T.

If

c

is in the range of

T,

c

=

Tf,

then

T(T*T)-’T*c

=

T(T*T)-’T*T~=

~f=

C.

This proves

fT*

=

P

=

Tf*.

U

The operation

{4/;

I

E

1)

-+

{$/;

I

E

J)

defines, in a

sense, a duality pperation. The same procedure, applied

to the frame

($/;

I

E

J),

gives the original frame

{4[;

1

E

J)

back again. We shall therefore call

(6,;

E

J)

the

dual

frame

of

{4/;

1

E

J).

The duality

4,-

4,

is also

expressed

by

(2.1.3); for any

f,g

E

2

we have

(f,g)

=

c

(f?$/)(4/A)

=

c

(f?4/x$/,g).

IEJ

I€J

In what follows we shall

so

often encounter

T*T

(rather

than

T

alone) that

it

makes sense to introduce a new

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

970

IEFF

TRANSACTIONS ON INFORMATION THEORY,

VOL.

36.

NO.

5,

SEI’TEMHFR

1990

notation for this operator. We define

- --

U=

T*T,

U=

T*T

=U-’.

In particular

U=

c

4/(4/,*)

AnlulBn

&=U-’(b/.

IcJ

Proposition 2.1 gives us an inversion formula for

T.

If the

elements

f

E

2

are characterized by means of the inner

products

((

f,c$/);

1

E

J),

then

f

can be reconstructed

from these by means of

f

=

Ci1<4/,f)

I

valid” choices

is

used, where

&/

is replaced by 2/3(4,

+

a).

Of all the possible “quasi-inverses” for

T, T*

is therefore

the only one that automatically projects sequences in

(RanT)

A

similar phenomenon occurs with the infinite-dimen-

sional frames we shall consider. While no finite number

of them will be linearly dependent, there generally do

exist convergent linear combinations, involving infinitely

many

+/,

which sum to zero. This again causes “recon-

struction formulas” to be nonunique, but again the

4l

=

will offer the optimal solution, in the sense that

they are the

only

choice leading to

to zero while effecting the reconstruction.

ZC,~,

=

0,

for all

c

=

(c/)/,~

I

RanR.

(2.1.4)

I

In (2.1.4) the vectors

&/

are defined by

&/

=U-’4,.

Note

that, in general, if the frame is redundant (i.e., contains

“more” vectors than a basis would), there exist other

v_ectors in

2

that could equally well play the role of the

4/

and lead to a reconstruction formula. This is due to the

fact that the

4/

are not linearly independent in the

general case. This phenomenon can be illustrated with

the two-dimensional example of Section

I-C.

Take

2

=

C2,

and define

4,

=e,,

+3

=

-

2“’

-

?e2

2

where

e,

=

(l,O),

e2

=

(0,l) constitute the standard or-

thonormal basis in

C2.

One can check very easily that for

all

U

E

X,

16

42

=

-

2“’

+

-e2,

23

2

c

1(4/4)l

=

-IlUll

3

2

I=1

so

that

U=

3/21, hence

becomes

=U-’+,

=

2/34,, and (2.1.4)

23

U

=

-

c

4/(4/,U>.

3

1=1

Since

C:=

,4/

=

0 in this example, it is clear, however, that

for any choice of

a

E

2,

an equally valid reconstruction

formula is given by

23

U

=

-

c

(4/

+

a)(4,,u).

3

I=1

The choice

a

=

0, corresponding to (2.1.4), is the “minimal

solution” in the following sense. The image, in C3, of

C2

under the frame operator

T

is the two-dimensional sub-

space with equation

x,

+

x2

+

x3

=

0; we denote this sub-

space by

RanT.

Vectors in

C3

orthogonal to

RanT

are all

of the type

c

=

A(1,1,1). When the components of such a

vector are substituted for the

(4/,~)

in (2.1.4), then the

“reconstruction” leads to

0,

since

This is easy to check by the following argument. Write

4/

=

U-’C$/

+

U,,

and suppose that (2.1.4) holds. It follows

that

Cu,(4,,f)

=

0, for all

f

E

2,

or

Cu,c,

=

0, for all

c

E

RanT.

The optimality condition implies

Cu,c,

=

0

for

all

c

1

RanT.

It follows that

Cu,c,

=

0 for all

c

E

12(J),

hence

U/

=

0 for all

1.

To apply (2.1.4) it is, of course, necessary to construct

the first. Writing

U

as 2(A

+B)-L[n

-(2(A

+B)-’U)l,

one has the following series for the

$/,

Since

A-B

2u

B-A

A+B A+B-B+A

nsn--<-

n

or

<1

(2.1

-6)

the series in (2.1.5) always converges. The closer B/A is

to

1,

the faster the convergence, of course.

Remark:

For the reconstruction formula (2.1.4) for

f

from its coefficients

($,,f),

we have used (2.1.3), namely

that

f*T

=

n.

One can also interpret (2.1.3) differently.

From

T*f

=

1

it follows that, for all

f

E

2,

f=

c

<&f>4/.

I

This tells us that any function

f

can be expanded in the

4/,

and gives

us

a recipe for calculating appropriate

coefficients. This is the point of view taken in so-called

“atomic decompositions.”

It

is thus clear that frames and

atomic decompositions are dual notions [481.

All the previous formulas become much simpler

if

the

frame

is

tight,

i.e.,

if

B

=

A.

In that case

u=An,

f=A-ln

&

=

A-@/

f=

A-’

c

4/(4/>f>.

It

J

If the frame constant for a tight frame is equal to one,

This is no longer the case

if

one of the other “equally

A

=

1, then the reconstruction formula looks exactly like

I=

1

I=1

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREOUENCY LOCALIZATION AND 5IGNAL ANA1

YSlS

~

97

1

the decomposition of a function with respect to an or-

thonormal basis,

f=

c

h(4l.f).

IEJ

In fact, if the vectors in a tight frame with frame constant

1

are all normalized, then the frame constitutes an or-

thonormal basis, as can easily be seen by the following

argument:

ll4k1I2

=

I

(4/?4k)

l2

IEJ

=l14k114+

c

I(4/?4k)12

IE

J

which implies

(41,4k)

=

0

for 1

#

k

if

ll+kll

=

1.

As

we

explained in the introduction, there are circumstances in

which one_ prefers to work with nontight frames. In that

case the

4)

have to be constructed explicitly from the

c$/.

Formula (2.1.5) then gives an algorithm for the computa-

tion of the

6,;

as (2.1.6) shows, it pays to have a ratio

B/A

as close to 1 as possible. Frames that are almost

tight (i.e.,

B/A

close

to

1) will be called snugframes. The

"snugness" can be measured by

S

=[B/A

-11-'. In the

examples below we shall encounter values of

S

2

100,

corresponding

to

B/A

of the order of 1.01 or even

smaller, for quite realistic frames (i.e., reasonably large

values of

po,

qO

or

a,,

bo-see Introduction).

Note also that, while in principle all the different

il,

1

E

J,

have to be calculated separately, in practice simpli-

fications may occur. Let us show what happens for the

discrete Weyl-Heisenberg coherent state frames and for

the wavelet frames defined in the introduction. We take

therefore

3

=

L2(R>,

J

=

Z2.

In the Weyl-Heisenberg case, we can rewrite

U

as

U=

C

W(mP,,nq")g( Wh,,nq,)g,

.>

m,n

E

h

where the operator

W(p,q)

is defined by [W(p,q)g](x)

=

eiPXg(x

-

9).

One easily checks that W(p,

q)W(p',

4')

=

e-'P'qW(p

+

p',q

+

4').

Using this multiplication for-

mula for the operators

W,

one easily finds that

W(

mp,,

nq,)T

=

TW(

mp,,

w,).

W(

mp,

,

nq,

)

U-

=

U-

'

W(

mp,,

nq,

.

Hence

This implies

(grnn)"

=T-'grnn

=

U-

'

W(

mp,,

9

w,,)

g

=

W(

mP0

7

n9,)T-

or

(gmn)"(x)

=

eirnpox(go0)'(x

-

nq,)

=

grnn(x>, where

=

(goo)-

=

T'g.

We have thus only one function to com-

pute, i.e.,

goo

=U-'g,

instead

of

a double infinity of

different (gmn)"(m,

n

E

Z).

If moreover

B/A

is close to

1, then the rapidly converging series (2.1.5) can be used

for this computation.

In the affine case, we find

U=

U(

a;;,ar

nb,,)h(

U(

ar,nr

nb,)h,

.)

m,nEH

where

[U(a,b)f](x)=

l~l-'/~f(x

-

b/a).

Again we can

use the composition law

U(

a',

b')U(

a",

b")

=

U(

a'"',

b'

+

a'b")

U(a~,O)T=UU(a;;,O).

to show that

Note that we have no translation in these U-operators; it

turns out that

U

does not commute with

U(ar,

nb,

a:)

if

n

#

0.

Since

U(ar,

ay

nbo)

=

U(a:,O)U(l,

nb,),

we find

(hrn,,)-

=

U(ar,O)U-'U(l,nb,)h

or

(

hmn)-( x)

=

hen)-(

a,"x).

The simplification is less drastic than in the WH case,

since only one of the

two

indices is eliminated, and one

still has to compute the infinite number of

(h,,)"

=

U-Ihtrn. In practice, however, only a finite number are

needed, and for the computation of these it is again a big

help

if

B/A

is close to 1.

Note that

if

one stops at the first term

(k

=

0)

in (2.1.51,

one obtains the approximate inversion formula

.-,

If

B/A

is close enough to one, this is a fairly good

approximation.

In

the first calculations with wavelets, the

formula used for analysis and reconstruction was

very

similar

to

(2.1.7) [25], without theoretical basis. It turns

out that in those frames

B/A

was indeed

vcry

close

to

1,

so

that

fapprox

is a good approximation

to

f.

B.

Tight Frames

1)

Explicitly Constructed Tight Frames: In this subsec-

tion we review shortly, for the sake of completeness, the

explicit construction

of

tight frames given in [16]. We have

drawn inspiration from [31] to make the construction

more elegant. For examples, graphs and a more detailed

discussion we refer to [16].

In both cases an auxiliary function

v

of the following

type is used

v:R-tR

If

v

is chosen to be a

Ck

(or

C")

function, then the

resulting frames will consist of

ck

(em)

functions.

a)

The Weyl- Heisenberg case: Choose

p,,

q,

>

0,

with

pO.qO

<

2~. (In Section 11-C we shall have more

to

say about this restriction.) We shall assume here that

po.qo

2

n-.

(See [16, Appendix] for indications how the

construction can be adapted

if

po-qo

<

T).

Define

A

=

27r/p0

-

qo;

one has

0

<

h

I

r/pO.

The function

g

is

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

912

IEEE

TRANSACTIONS

ON INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

fi(Y)=(10gao)-'/2(

then constructed as follows:

sin[

:U(

)]7

1

I

y

5

a,l

cos['u(

Y-a,l

)]

a,lIy5a;l

2 la,(a,-1)

'

71.

I

sin

[

iv(

A-'(

+

x))],

-

r/pi,

I

x

I

-

+

A

PO

-+A

71.

I

x

<--A

71.

Po

PO

71.

7T

I

COS[

:U(

A-'(

x

-

+

A))],

-

A

5

x

5

r/p0

PO

The overall factor

qo1I2

normalizes

g;

one easily checks

that

ldxlg(x)I2

=

1.

The following two properties of

g

are

crucial.

These two properties together ensure that the

gmn,

g,,Jx)

=

eimpOxg(x

-

nq,),

constitute a tight frame. By

Plancherel's theorem we have indeed for all

f

E

L2(R),

One finds thus

gm,(x)

=

G(x)-'gmn(x),

and the inversion

formula becomes

Remark:

If the function

U

is chosen to be

C",

then

g

is

a compactly supported C"-function. While the uncertainty

principle can of course not be violated, this nevertheless

allows fairly good localization of

g

in

both time and

frequency. The coefficients

(g,,,

f

)

do therefore corre-

spond to a reasonably accurate time-frequency localized

picture of the signal

f.

Moreover, there exists a constant

A

=

271./p,.q,

such that

where we have used the notation

g(y)*

to denote the

complex conjugate of

g(y).

Note that the same calcula-

tion can be made whenever lsupport

gl

I

271./p0,

even

if

(2.2.1)

is not satisfied.

In

that case the operator

U

of

Section

11-A

reduces to multiplication by the periodic

function

G(x)

=

271.p~'C,,,Ig(x

-

nq,,)12

(see also

[50]).

2

The role of this constant

A

is crucial. If one restricts

oneself to

A

=

1,

then this forces the

g,,

to be an

orthonormal basis, which leads to functions

g

that are

badly localized in either time or frequency. This is a

consequence of the Balian-Low theorem

[51], [52]

(Theo-

rem

2.3

next), rediscovered in

[53].

As

soon,

however, as

one allows

A

#

1,

the picture changes drastically, and

much better time-frequency localization is attainable.

b) The wavelet case:

In

this case there are

no

a

priori

restrictions

on

the choice of the parameters

a,,

bo,

other

than

a,

#

0

or

1

and

6,

#

0.

We may choose, without loss

of generality,

a,

>

1,

and

b,

>

0.

Define

1

=

271./[b,(a:

-

l)].

The tight frame of wavelets will be based

on

the

function

h

with Fourier transform

fi

constructed as fol-

lows

[16]:

y5l

11-1

\1

(2.2.2)

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

973

The function

h

itself is given by the inverse Fourier

transform,

The normalization of

h

has been chosen

so

that

/dYlYl-’ll;(Y)[2

=

1.

2)

C

l+6Y)12

=(log%-lX[o,m,(Y)>

The following

two

properties of

h

are again crucial:

1)

Isupport

l;~

=

(ai

-

I)/

=

2r/b,,

(2.2.3)

k=Z

where

x[,,,,)

is the indicator function of the right half line,

X[,,~)(Y)

=

1

if

y

2

0,

x[,,,,,(y)

=

0,

otherwise. These prop-

erties together enable us to construct a tight frame based

on

h.

By Parseval’s theorem, we have, for all

f

E

L2(R),

C

I(hmn,f)12

m,n=Z

m,n

E

L

(2.2.4)

If we define

h+

=

h, h-

=

h*

(i.e.,

(h-

T

(k)

=

fi(

-

k)),

then this calculation shows that the

(h&;

m,n

E

Z)

con-

stitute a tight frame. Specifically,

llfl12.

(2.2.5)

C

I(hLn7f)l

==

2

27.r

€=+or-

m,nEL

Similarly the

(h‘,“:;

m,

n

E

h,

A

=

1

or

21, with

h(’)

=

Re

h,

h‘”

=

Im

h,

constitute a tight frame. Strictly speaking, the

frames

(h;,;

E

=

+

or

-,

m,n

E

Z)

or

(h‘,“:;

A

=

1

or 2,

m,n

E

Z)

are not quite of the type described in the

introduction, since they are not obtained by dilating and

translating one single function.

As

shown by the computa-

tion leading to (2.2.4), the operator

U

=

T*T

handles the

positive and negative freque2cy domains independently.

Since the Fourier transform

h

of

h,

defined by (2.2.2), is

entirely supported on the positive half line, the use of a

second function, which will handle the negative frequen-

cies, is therefore unavoidable. In other examples (see e.g,

Section 11-C-2) the function

h

will be chosen such that

h

is supported on both the negative and the positive half

lines, and one function suffices.

Let us return to the construction (2.2.2). For a special

set

of

signals

f

Lo

be analyzed, one may restrict oneself,

even if support

h

c[O,m),

to only one basic function

h,

and the associated wavelets

h,,,,,.

This happens if one

knows

a

priori,

as is often the case, that the signal

f

is

real. Since then

f(

-

y)

=

f(y)*,

one finds

As

for the Weyl-Heisenberg case, a calculation similar to

(2.2.4) can be carried out whenever the support width

of

h

is smaller than 27r/b,, even

if

(2.2.3)

is

not satisfied.

The operator

U

becomes then

(Tf)^(Y)

=

fi(Y)f(Y)

with

or, equivalently,

Hence

In the construction of the orthonormal basis,

in

1

1311, the

procedure starts in the same way. The function

v

is

chosen to be

C”,

and has one additional property,

(2.2.6)

The “doubling” (using superscripts

+

to be able to cover,

in Fourier space, the whole real line instead of only the

half line) is avoided in [31] by incorporating also the

mirror image

of

h

into the basis function

I,/J.

Explicitly,

v(

x)

+

v(

1

-

x)

=

1,

for all

x

E

R.

Due to the extra property (2.2.6) of

v,

one easily checks

that

11$112

=

jk

II,/J(x)12

=

1.

Note that the size of the

support of

6

is no longer equal to 2r/b,,

so

that the

straightforward calculation made previously no longer

works. In fact, the set of functions

I,/Jmn(x)

=

U,~/~I,/J(U;”~

-

nb,),

m,

n

E

Z,

turns out to be an or-

thonormal basis of

L2(R)

as the result of some miraculous

cancellations, for which the property (2.2.6) of the func-

tion

v

turns out to be quite crucial [31]. These cancella-

tions occur only when

a,

takes on a very special value,

namely when

k+l

a,

=

-

with

k

E

N.

k’

The case

k

=

1, or

a,

=

2, corresponds to

Y.

Meyer’s

construction in [31]. With

b,

=

1

(as in [311),

Y.

Meyer’s

basic wavelet is thus given by

1

f(

y)

=

-e’y/2[w(

y)

+

w(

-

y)]

(2.2.7)

fi

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

974

IEEE

TRANSACTIONS ON

INFORMATION THEORY, VOL.

36,

NO.

5,

SEPTEMBER

1990

with

4Y)

=

4rr

3

8rr

3

where

v

is a

C"

function from

R

to [0,1] such that

v(y)

=

0

for

y

I

0,

v(y)

=

1

for

y

2

1 and

v(y)+

v(1-

y)

=

1

for all

y.

As

pointed out in the introduction, the

concept of multiscale analysis allows one to understand

more deeply why this construction works,

so

that the

"miraculous cancellations" just mentioned become less

2)

Relations Between the Frame Parameters and the

Frame Bounds:

In the explicitly constructed tight frames,

the frame constant

A

is given by

A

=

27r/p0q0, for the

Weyl-Heisenberg case, and by

A

=

rr/

b,

log

a,,

for the

affine or wavelet case. This is no coincidence. We show in

this subsection that these values for

A

are imposed by the

normalizations chosen for

g,h,

and are independent of

the details

of

the construction, i.e., they are generally true

for

all

tight frames. More generally, we prove inequalities

for the frame bounds

A,

B

for

all

Weyl-Heisenberg

frames or wavelet frames, tight or not.

a)

The

Weyl-

Heisenberg case:

Let us assume that the

(+",,;

m,n

E

Z)

are an arbitrary frame of discrete

Weyl-Heisenberg coherent states, with frame constants

A,

B,

and lattice spacings

p,,

q,,

i.e.,

+mn(

x)

=

eimpox+(

x

-

nq,),

so.

Allfll'

l

c

I

(+,,,f)

l2

I

Bllfll'.

m,n

We shall see next that a frame is possible only if

po'qo

I

257. Let

us

therefore restrict ourselves to this case. Then

there exists, for the same values

po,qo,

a tight frame

This is true for any Weyl-Heisenberg-frame with lattice

spacings

pO,

qo.

In particular,

if

the

c$",,

constitute a tight

frame (i.e.,

A

=

B),

then necessarily

2rr

Po40

A

=

-114112.

a)

The wavelet case:

In this case also we shall derive

inequalities similar to (2.2.9). Since there is no equivalent

to (2.2.8) for wavelet frames, the derivation will be slightly

more complicated. Let us assume, again, that

(c$mn;

m,n

E

H)

is an arbitrary frame

of

wavelets, with lattice spac-

ings determined by

a,,

bo,

and with frame constants

A,

B,

i.e.,

+,,,(

X)

=

U,"/'+(

aomx

-

nb,)

Allfll'

I

c

l(+mn,f)

1'

I

Bllf1I2.

(2.2.10)

m,n

Take now any positive operator

C

which is trace-class,

i.e., which is

of

the form

c

=

cc,uI(u,,

*)

1

where the

uI

are orthonormal,

c,

>

0

and tr

C

=

C,c,

<W.

Then (2.2.10) implies

l

1

m,n

1

or

We shall apply this to the following operator,

da db

U'

c

=

//

-h(",b)(

*

)t

(

a,

b)

(2.2.12)

constructed with the help of the affine coherent states

introduced in SeFtion I-D. The function

h

E

L2(R)

should

satisfy

Jdy

lyl-'lh(y)I2

<w

(see Section I-D). Here

t(a,

b)

is a positive function in

L'(R*

x

R;

a-'dadb).

The opera-

tor (2.2.12) is positive and trace-class, with

da db

tr

C

=

/Tt(

a,

b)

{gmn;

m,n

E

HI

with

llgll=

1.

(For

po-qo

<

2rr, we take

g

as constructed in Section 11-B-la); for

pn'qn

=

2rr, take

where we have assumed

llhll=

1.

On the other hand,

--

g(x)

=

4;

'1'

if

1x1

I

4,

/2,

g(x)

=

0,

otherwise). One eas-

ily checks that

It follows that

=

1

(+,U(

a{",agrn

nb,)-'U( a,b)h)l't(a,b)

(

+mn,

C+,,>

(g,

4

-m -n

>

.

(2.2.8)

da db

=

(+,U(a;",a,"

nb,)-'CU(a~",a~" nbo)4)

(

gmn,

4)

=

e-imflP,19,

(2.2.13)

where we have used the composition law

of

the U-oper-

Similarly

Bllg112

2rr~P0q,~~+~~2. Since

llgll

=

1,

we

find

AI-II411

2rr

2

IB.

(2.2.9)

ators. We now restrict ourselvks to functions

t

of the form

t(a, b)

=

X[I,",,[(

lab . tl(

b/

1.1)

where

XL1,",,)

is the indicator function

of

the half open

Po40

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL. ANALYSIS

915

interval

[l,

an),

i.e.,

,y~l,ol,p

=

1

if

1

5

U

<

a,,,

0

otherwise.

Since

~rn,y~I,oo)(al;llal)

=

1,

(2.2.13) then leads to

m,n

C

(4rnn,C4rnn)

This sum over

n

can be estimated by the following lemma.

Lemma

2.2:

Let

f

be a positive, continuous, bounded

function on

R,

with

f(x)

+

0

as

1x1

--)W.

Assume that

f

has a finite number of local maxima, at

xi,

j

=

1;

.

.,

N.

Define

x,-S+I

Ai=

sup

1

hf(x).

SE[O,I]

x,-a

Then

For the sake of completeness we provide a proof for the

case

N

=

1;

the case for general

N

can be proved analo-

gously, though the inequalities can be sharpened

if

some

of

the

xi

are within a distance

1

of each other.

Proof:

Let

n,,

be the largest integer not exceeding

xl,

the point where

f

reaches its maximum. Since

f

is in-

creasing on

(-m,xl]

and decreasing on

[xl,m),

and since

no

I

x,

<no

+1:

maximum, at

x

=

xl,

then

m

hf(x)-f(x,)

5

c

f(n)

5j-m-mw(x)+f(xl).

/_b

n

=

--m

Let us apply this to (2.2.14). Choose

F

to be any positive,

continuous

L1

function on

R,

tending to zero at infinity,

with one local maximum, at

x=O.

Choose

A>0,

and

define

tl(

x)

=

F(

AX).

Applying Lemma 2.2 to (2.2.14) then leads to

or

2

=

-

log

ao./duF(x).

(2.2.16)

A

Inserting (2.2.15) and (2.2.16) into (2.2.111, and taking the

limit for

A

--)

0

leads

to

T

jdy

Iyl-'If(

y)

1'

I

B.

(2.2.17)

AI-

bo

1%

a0

These inequalities hold for

any

frame

of

wavelets

$rnn

Incidentally, (2.2.17) shows that the basic function

4

for a

frame of wavelets must 2atisfy the same "admissibility

condition," i.e.,

/dylyl-'14(y)12

<CO,

as the functions from

which continuously labeled affine coherent states are con-

structed (see Section I-D). In particular, if the

4rnn

consti-

tute a tight frame

of

wavelets, then

In the explicitly constructed tight frames in Section II-B-

lb,

two functions (either

h

*,

with

h+

=

h,

h-

=

h*,

or

h(*),

A

=

1,2, with

h(I)

=

Re

h,

h(')

=

Im

h)

were needed to

construct tight frames of wavelets (i.e., the

h;,,

or the

h',":,

A

=

1,2). For such frames the arguments lead to the

frame constant

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

976 IEEE TRANSACTIONS ON INFORMATION THEORY,

VOL..

36,

NO.

5,

SEPTEMBER 1990

This agrees with the value

A

=

257/

bo

log

a,,

obtained in

Section 11-B-Ib (see (2.2.5)), sinFe we chose the normal-

ization of

h

such that

{dy lyl-'lh(y)l2

=

1.

C. General (Not Necessarily Tight) Frames in

L2(

R)

-

Ranges for the Lattice Spacings

-

Frame Bounds

As we already explained in the introduction, it may be

necessary in some applications to resort to nontight

frames. This can be the case

if

the basic function

g

or

h

is

imposed

a

priori

(because

of

its adaptation to the problem

at hand), or in the case of wavelets, when the explicit

examples of functions

h

leading to tight frames are too

spread out.

In this section we treat the following questions:

1) Is there a range of parameters that is excluded

a priori

(i.e., independently of the choice of

g

or

h)?

2) Given

g

(or

h),

determine a range

R

for the param-

eters

po,qo

(resp.

ao,bo)

such that

if

(po,qo)

E

R

(resp.

(ao,

bo)

E

R),

then the associated

g,,

(resp.

hmn)

constitute a frame.

3) For

g,po,qo

(or

h,ao, bo)

chosen as in 21, compute

estimates for the frame bounds

A

and

B.

In order to interrupt the flow of the exposition as little as

possible, we relegate all the technical proofs for this

section to Appendix

C.

1)

The

Weyl-

Heisenberg Case:

a)

Critical value for the product po. qo:

In the

Weyl-Heisenberg case there exists a critical value, 257,

for the product

po.qo.

This is already illustrated by the

construction in Section 11-A-la), which only works

if

po.qo

<

257. The following theorem states that at the

critical value

po*qo

=

257, only functions

g

that are either

not

very

smooth or do not decay very fast can give rise to

a frame.

(Balian

-

Low

-

Coifman

-

Semmes):

Choose

gE

L2(R),

po

>

0.

If the

g,,

associated with

g,po,qo

=

2n-/p0,

constitute a frame, then either

xg

E

L2

or

g'

E

L'.

Remark:

This theorem was first published by

R.

Balian

[51] for the case where the

g,,

are an orthonormal basis.

In the 1985 Festschrift for the 60th birthday of the physi-

cist

G.

Chew,

F.

Low also discusses this problem [521. He

gives (independently) essentially the same proof as in [511.

The proof presented in [51], [52] contains a technical gap

that was filled by

R.

Coifman and

S.

Semmes. The proof

extends easily from the basis case to the frame case. We

give here the proof as completed by

R.

Coifman and

S.

Semmes.

The proof of Theorem 2.3 uses the Zak transform

U,.

This transform maps L2(R) unitarily onto L2([07 112); it

was first systematically studied by J. Zak [541, in connec-

tion wjth solid state physics. Some of its properties were

known long before Zak's work, however. In [551 the same

transform is called the Weil-Brezin map, and it is claimed

that the same transform was already known to Gauss. It

Theorem

2.3

was also used by Gel'fand (see, e.g., Ch. XI11 in

[561).

J.

Zak seems, however, to have been the first to recognize

it as the versatile tool it is and to have studied it systemat-

ically. It has many very interesting properties; its applica-

tions range from solid state physics to the derivation, in

[57], of new relationships between Jacobi's theta func-

tions. Before embarking on the proof of Theorem 2.3, we

briefly review the definition and some of the properties of

U,.

The Zak transform

U,

is defined by

(Uzf)(t,s)

=A'/2

e2T'f'f(A(s-1))

(2.3.1)

where the parameter

A

>

0

can be adjusted to the prob-

lem at hand. For the proof of Theorem 2.3 we shall take

Strictly speaking, the definition (2.3.1) does only make

sense for the subspace of the L2-functions for which the

series converges. It is, however, easy to extend (2.3.1)

from those functions for which it is well-defined, to all of

L2(R). One way of doing this is to observe that the images

under (2.3.1) of the orthonormal basis

emn

of L2(R),

ItL

A

=

40.

x[O,

A)(

-

nA)

(

7

E

'1

e,,(x)

=

A-'/2e2T'mx/A

are well-defined, and constitute again an orthonormal

basis of L2([0, 112),

(

Uze,,)(

t,

s)

=

e-2T"ne2T'ms.

It follows that (2.3.1) defines a unitary map from

L2(R)

to

L2([0,1l2).

On the other hand, (2.3.1) can also be ex-

tended to values of

(t,

s)

outside

[0,

112.

For

f

E

L2(R), the

resulting function is in L~,,(R2>, and satisfies

(Uzf)(t+W

=

(Uzf)(t74

(

Uzf)(

t,

s

+

1)

=

e2Trt(

U,

f

)(

t,

s)

(2.3.2)

almost everywhere (ax.) with respect to Lebesgue mea-

sure on

R2.

A

rather remarkable consequence of (2.3.2) is

the following. Suppose that

f

is such that

U,

f

is continu-

ous (on

R2).

Then

U,f

must necessarily have a zero in

[0,1l2. The proof of this fact, first pointed out in [581, is

quite simple. The presentation given here is borrowed

from [59]. If

U,f

had no zero in [0,112, then logUzf

would be a univalued, continuous function on [0,1l2 ex-

tending to a continuous function in

R2

by (2.3.2). On the

other hand, (2.3.2) implies that

(logUzf)(t +l,s)

=

(logU,f)(t,s)

+257ik

(log

Uzf

) (

t

,

s

+

1)

=

(log

Uzf

) (

t

,

s

)

+

2

Tit

+

2

Til

(2.3.3)

where

k,

1

are integers, independent of

t,

s

because of the

continuity of log

U,

f.

But (2.3.3) leads immediately to the

following contradiction:

0

=

(log

U,f

)

(0,O)

-

(1%

U,f)

(

1

9

0)

+

(1%

Uzf)

(

1

,o>

-

(log

Uzf

17

1)

+

(1%

Uzf

(

19

1)

-

(log

Uzf

)(O,

1)

+

(log

Uzf

)(07

1)

-

(1%

Uzf

)(O,

0)

=

-

2n-ik

-

2n-i

-

257il+

2rik

+2n-il=

-

2rri

#

0.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

977

This proves that we started from a false premise, i.e., that

Uzf

has a zero in [0,1l2. A similar argument proves

Theorem

2.3.

The above is only one of the many proper-

ties

of

the Zak transform. For more of these properties,

and interesting applications of the Zak transform to sig-

nal analysis, we urge the reader to consult [60].

The images, under the Zak transform,

of

functions

g,,

(with

po*qo

=

27~1,

are remarkably simple. One easily

checks that, for the choice

A

=

qo,

(Uzgm,)(

t,

s)

=

e2Timse-2Ti‘n(UZg)(

t,

s).

(2.3.4)

An

immediate consequence of

(2.3.4)

is

C

I

(gmntf)

I’

=

C

I

(UZgrnn, UZf)

I’

m,n

It follows that the

g,,

constitute a frame, with frame

bounds

A,

B,

if and only if, for (t,s)E[O,1l2 a.e. (and

hence, by

(2.3.2),

for

(t,s)

E

R2

a.e.)

All2

I

I(Uzg)(t,s)

I

B1l2.

This is another crucial ingredient

of

the proof of Theorem

2.3,

to which we now turn.

Proof of Theorem

2.3:

Suppose that the

g,,

consti-

tute a frame, and assume also that

xg,

g‘E

L2(R).

We

want to show that this leads to a contradiction. Define

G(t,

s)

=

(U,gXt,

s).

Since the

g,,

constitute a frame, we

have

a~lG(t,s)I~

b

(2.3.5)

for some

a

>

0,

6

<m,

and for

(t,

s)

E

R2,

a.e. For com-

pactly supported

f

one finds

[U,($)]

(t,

s)

=qi/2s(~Zf)(t,s)

-q03/2Ce2.rrir‘lf(qg(s-~))

I

This shows that

xg

E

L2

implies

a,G

=

a,(U,g)

E

L;,,(R2).

Similarly

g‘

E

L~

implies

a,G

E

L;,,(R~).

If the square integrability of the partial derivatives

of

G

implied that

G

was continuous (which it does not, since

we are in more than one dimension), then the proof

would be finished. By the argument given before the

proof, inf

IC1

would then be zero, which is in contradic-

tion with

(2.3.5).

This is essentially the argument of Balian

in [HI, where the implicit assumption that

G

is continu-

ous seems to be made. Lemma

2.4,

due to

R.

Coifman

and

S.

Semmes, which we state below, shows how the

boundary conditions

(2.3.21,

together with the bounds

(2.3.51,

lead to a contradiction, without assuming continu-

ity for

G.

The main idea is to use an averaged version of

G.

This averaged function is automatically continuous,

and, if the averaging is done on a small enough scale,

close enough to

G

so

that the properties inherited from

(2.3.5)

and

(2.3.2)

still lead to a contradiction. This then

proves Theorem

2.3.

0

Lemma

2.4:

Assume that

G

is a bounded function on

R2

that is locally square integrable and which satisfies

G(t+l,s) =G(t,s)

G(t,s+l) =e2TrfG(t,s).

If both

a,G

and

d,G

are locally square integrable, then

essinf,,,,,,,

IG(t,s)l=

0.

Here the “essential infimum”

of

a measurable function

f

is defined by

essinf

f

=

inf

{A;

I{

x;

f(

x)

I

A)

I

>

0)

where

IVI

denotes the Lebesgue measure of the set

V.

This definition avoids values taken by

f

on sets

of

mea-

sure zero. For instance, for

f(x)

=

l

for

x

#

0,

f(0)

=

0,

one has inf

f

=

0,

but essinf

f

=

1.

Proof of Lemma

2.4:

This proof is rather technical; it

0

Note added

in

proof

After this paper was written,

G.

Battle produced a very elegant new proof

of

Theorem

2.3

which avoids the use of the Zak transform [69].

Battle’s paper only treats the case where the

g,,

are an

orthonormal basis (as did the original papers by Balian

and Low). His argument was extended to frames by

A.

J.

E.

M. Janssen and I. Daubechies [70].

For the critical value

po-qo

=

2~

we see thus that not

much regularity and/or decay can be expected from a

function

g

leading to a frame. This is in marked contrast

with the case

po-qo

<2~.

In that case, as shown in

Section 11-B-la, there even exist C”-functions

g

with

compact support such that the associated

g,,

constitute a

tight frame.

This critical value

po.qo

=

27r,

has a physical meaning.

As shown by Fig. l(a),

(po.qo)-l

is the density, in phase

space, of the discrete lattice of functions

g,,.

The density

(27r)-’

is nothing but the Nyquist density; it is well-known

in information theory that time-frequency densities at

least as high as the Nyquist density are needed for a full

transmission

of

information. It is therefore not surprising

to encounter this same critical value here. One encoun-

ters the same argument in quantum physics, often used in

semiclassical approximations, where a complete set

of

independent states (i.e., a set

of

linearly independent

functions in

L2(R)

whose linear combinations span a

dense subspace in

L2(R))

heuristically corresponds to a

density

(257)-’

in phase space. In other words, every state

“occupies” a “cell” of area

27r

in phase space.

For

po.qo

>

27r,

the intuition from physics or informa-

tion theory suggests that the associated phase space lat-

tice is “too loose,” i.e., that the

g,,

cannot span the

whole Hilbert space. More precisely, we expect that for

is given in Appendix B.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

978

IEEE

TRANSACTIONS

ON

INFORMATION

THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

any

g

E

L2(R), there exists at least one

f

E

L2(R),

f

#

0,

such that

(g,,,

f)

=

0

for all

m,n

E

Z.

This is indeed the

case.

If

po.qo

/27r

>

1

is rational, then the following argu-

ment, again using the Zak transform, shows how to con-

struct a function

f.

By a dilation argument we can restrict ourselves to the

case

po

=

277,

q,

=

K/L, with K, L

EN,

K

>

L

>

0.

Let

F,

G, G,,

be the Zak transforms of respectively

f,

g, g,,,

as defined by (2.3.11, where we take

h

=

1. Then

Gm,(

t,

s)

=

e28imSG

t

s

-

n

-

i3

3

For

n

=

kL

+

I,

with

I,

k

E

Z,

0

I

<

L, this reduces to

G

t

S--K

(7

3

G

(

t,s)

=

e2srims

-27rikK1

mn

where we have used (2.3.2). The function

F

will be

orthogonal in L2([0,112) to each

G,,

if, for all

s

~[O,ll

and for all

k,l

EZ

with

051

<

L,

cdrF(r,s)e-2"kK'G

t,s

-

-K

=

0.

(2.3.6)

i

li

We can rewrite (2.3.6) as

['Kdfe-2srikK1

K-1

G(r

+-,s--K)F(r+:,s)=O.

m1

m=O

KL

(

2.3.7)

We are thus led to the linear system

of

equations

K-1

A,,(t,s)+,(t,s)=~

OSI<L (2.3.8)

m=O

where

m

)

(2.3.9)

+,(t,s)=F

t+-

s

.

(

2.3.10)

Since the system (2.3.8) has L equations for K

>

L un-

knowns, it always has a nonzero solution, for every pair

(t,s)

E

[O,l/K)x [0,1]. The

+,(r,

s)

solving (2.3.8) can,

moreover, be chosen in L2([0,1/K)X[0,1]). One way of

doing this

is

to choose a fixed

U

E

CK,

and define

+,&,

s)

=

lim.

~~

u,(t,

s;

T),

where

u(t,s;T) =exp[-~A*(t,s)A(t,s)]u.

Clearly Ilu(t,s;

T)II*

I

llu1I2;

hence

C$=,l+,(t,

s)12

I

llu1I2.

On the other hand, since all the

A,,

are in L2([0, 1/K)X

[0,1]), the u(t,s;~) are clearly measurable in

t,s;

as

pointwise limits of measurable functions, the

4,

are

measurable too. Putting the

6,

together according to

(2.3.10) then defines a function

F

in L2([0,1I2) which is

orthogonal to all the

G,,.

Note that while

F

may be zero

a.e. for some choices of

U,

it is impossible that the

functions

F(u,)

associated with K linearly independent

vectors

U,;

.

3,

uK in

CK

all be zero a.e., since this would

mean that

A*(t,

s)A(t,

s)

>

0

a.e. in

t,

s,

which contradicts

(

"K.1

rank

[

A(t,

s)]

<

K. For appropriately chosen

U

E

CK,

the

previous construction leads thus to a nontrivial function

F

E

L2([0, 112) orthogonal to all the

G,,.

This argument does not work if

p,.

q,

/27r is irrational.

It is nevertheless still true that the

g,,

do not span

L*(R), whatever

g

in L2(rW) is chosen, even for irrational

values of po-qo/27r. The only proof that

I

know of this

fact uses von Neumann algebras; it was pointed out

to me by R. Howe and T. Steger. The proof consists

in the computation of the coupling constant of the von

Neumann algebra spanned by the Weyl operators

(W(mp,,

nq,);

m,

n

E

Z).

The coupling constant for this

von Neumann algebra was computed explicitly by

M.

Rieffel [49]; for

po.qo

>

27r it is larger than 1, which

implies that the von

Neumann algebra has no cyclic

element. This means that for any

g

E

L2(R), the closed

linear span of the

g,,

is a proper subspace

of

L2(R),

which was the desired result. Unfortunately, this proof

does not seem very illuminating from the signal analyst's

point of view.

Note added

in

proofi

Recently H. Landau [71] found

a different, intuitively much more appealing argument to

prove that the

g,,

cannot constitute a frame if

po'qo

>

27r. His proof works for all

g

which are reasonably "nice"

(decaying in both time and frequency).

This concludes what we have to say about the critical

value

(po.qo

=

277-1 in the Weyl-Heisenberg case. We

shall always assume

po.qo

I

277 in what follows.

6) Ranges for the parameters

po,

qo,

and estimates for

the frame bounds:

In the preceding subsection we have

excluded parameters

p,,

q,

for which

p,.

q,

>

277. Even

if

po.qo

I

277-, however, we do not automatically have a

frame for arbitrary functions

g.

When, for example,

g(x)

=

1

for

0

I

x

2

1,

and

g(x)

=

0,

otherwise, the

g,,

can-

not constitute a frame

if

qo>

1,

even

if

po*qo<27r.

Indeed, for

q,

>

1,

one finds that

(g,,,

f)

=

0,

for all

m,

n

E

Z

if the support of

f

c

[l, q,], independently of the

choice of

p,.

This is thus a case where an inappropriate

choice of

q,

excludes the possibility of a frame, for all

values of

p,.

The theorem below gives sufficient conditions on

g

and

q,

under which this cannot happen, i.e., there always exist

some

po

>

0

(in fact, a whole interval) leading to a frame.

Theorem

2.5:

If

1)

m(g;q,)=

essinf

~lg(x-nq,)12>0

(2.3.11)

2)

M(

g

;

q,)

=

esssup

I

g(

x

-

nq,)

l2

<w

(2.3.12)

and

3) sup[(l+s2)'I+€"2p(s)]

=~,<w

forsomec>~

where

p(s)=

sup

c

Ig(x-nq,)IIg(x+s-nq,)I

x

E[O,quI

n

x~[O,q~l

n

S€R

x

E

[o,

4,,1

n

E

L

(2.3.13)

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREVUENCY LOCALIZATION AND SIGNAL ANALYSIS

979

then there exists a

Pi

>

0

such that

Theorem

2.6:

Assume that

(2.3.11), (2.3.12), (2.3.13)

are

satisfied. Define

Vp,

E

(0,

Pi)

:

the

g,,

associated with

g

,

P,

,

qo

I

I/’

1

p;=inf

po

p

-k

P

--k

2Tm(g;qo)

.

[

lkIl[

(:

)

(

:

)]

are a frame

VS

>

0:3p, in [Pi,

Pi

+

61

such that the

gm,

associated to

g,

p,,

q,

are not a frame.

Proofi

see Appendix C.

0

The conditions

(2.3.11)-(2.3.13)

may seem rather tech-

nical. They are, in fact, extremely reasonable. Condition

(2.3.11)

specifies that the collection of

g

and its translates

should not have any “gaps.” This already excludes the

example given at the start

of

this subsection. The condi-

tions

(2.3.121, (2.3.13)

are satisfied

if

g

has sufficient

decay at

03,

in particular, if

Ig(x)l

I

C[1+ x21-3/2.

Note that both

(2.3.11)

and

(2.3.12)

are necessary con-

ditions. If

(2.3.11)

is not satisfied, then for every

E

>

0

one

can find a nonzero

f

in

L2(rW)

such that

C

1

(gm,,f>

1’

I

~II~II~

m,n

which means there exists no nonzero lower frame bound

A

for the

g,,.

Similarly there exists no finite upper frame

bound

B

for the

g,,

if

(2.3.12)

is not satisfied.

Remarks

1)

At the end of the preceding subsection we showed

that the

g,,

can constitute a frame only if

po-qo

I

277.

Hence necessarily

Pi

I

2~/q,.

2)

The set

{po;

the

g,,

associated to

g,p,,q,

consti-

tute a frame) with

g

and

q,

fixed need not be

connected. It is possible that this set contains values

of

po

larger than

Pi.

An

example is given by the

following construction. Let

4

be a

C”

function with

support

[0,

1/31

such that

141

has no zeros in

(0,1/3).

Define

g

by

0,

YIO

4(Y),

g(~)=

4(~-1/3), 1/3~~12/3

0

I

y

I

1/3

+(y-2/3), 2/3_<y11

I

0,

y2l.

Take

q,

=

27r.

Then, since support

2

=

[O,

11,

c

I

(

gmn

9

f

)

I

=

/dy

c

lg(

Y

-

)

I

fi

Y

)

I

m,n

m

This implies that the

g,,

constitute a frame

if

and

only

if

infC,Ig(y

-

mp0>l2

>

0.

Consequently

PO’

=

1/3,

while the set

of

all

po

leading to a frame is

(0,1/3)U(1/3,2/3).

For reasonably smooth

g

with sufficient decay at

m,

the

constants

m(g;

q,),

M(g;

q,)

and the function

P(s)

can

easily be computed numerically. These constants are use-

ful in estimations of the frame bounds

A,B,

as the

following theorem shows.

Then

p;

I

Po’,

and for

0

<

po

<p&

the following esti-

mates for the frame bounds

A,

B

holds

Proof

see Appendix C.

U

These bounds for

A

and

B

can be improved by the

following observation. If the

g,,(x)

=

eimpoxg(x

-

nq,)

constitute a frame, then

so

do the

where

2

denotes the Fourier transform of

g.

It follows

that

A2

(

gmnIA

(

C)

=

e-ins(~Li(

c

-

m~,)

9

(2.3.14)

B_<

(2.3.15)

Here

M($;p,),

m(g;pO)

and

b(s)

are the obvious exten-

sions of the quantities in

(2.3.111, (2.3.121,

and

(2.3.13).

For instance,

b(s)

=

SUP

C

16(5+mPO)Ilg(5+s+mP,)l.

5

E

[O,

pol

m

E

.Z

Similarly, one has the following better lower bound for

pi,

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

980

IEEE

TRANSACTIONS

ON

INFORMATION

THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

0.4

0.3

0.2

0.1

0

-0.1

C)

Examples

i)

The

Gaussian case

In this case

g(x)

=

T-1/4e-~2/2

(2.3.17)

This is the basic function for the so-called “canonical

coherent states” in physics

151.

It is also the basic function

chosen by Gabor

[l]

in the definition of his expansion. In

the notations used in this paper, Gabor’s approach

5

-

0

-

-5

0.20

I

-0.05

I

-10

-5

0

5

10

(a)

0.3

0.2

0.1

0

-0.1

-

10

-5

0

5

(b)

amounts to writing an expansion with respect to the

g,,

associated to

g,

po,

qo,

where

po.

qo

=

277.

This choice

seems very natural from the point of view of information

theory, since it corresponds exactly to the Nyquist density.

However, since both

xg

and

g’

are square integrable in

this case, Theorem

2.3

tells

us

that the

g,,

cannot

possibly constitute a frame. In fact, the Zak transform

U,g

of

g

(see Section 11-C-la) can be constructed explic-

itly in this case; it is one of Jacobi’s theta-functions, and it

-0.2

I

-

10

-5

0

5

10

1

.o

0.5

0

-0.5

-10

-5

0

5

(e)

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

981

DAUBECHIES: THE WAVELET TRANSFORM. TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

has a zero in (1/2,1/2) [21, [31, [601, [631. The operator

U

of Section 11-A is unitarily equivalent with multiplication

by

IUzg12

on

L2([0,

112),

and is therefore one-to-one, but

it has an unbounded inverse, i.e.,

~~~~EL~(R)II~II-~

C

I

(hmn>f)

1'

=

0.

m,n

One can still write an expansion of type

f

=

C

gmn(grnn,f)

m,n

but this expansion has, in general, bad convergence prop-

erties because

g

L2(iw)

(since

U,g

=

U,(T-'g)

=

lUzgl-2Uzg

has a pole at (1/27 1/21, and is therefore not

in Lz([0,112)). It is this fact that makes the expansion

associated to the Gabor wave functions unstable [2], [3],

[601. The function

g

was explicitly constructed in [2]; it

turns out to be discontinuous as well as nonsquare-inte-

grable (see Fig.

4(f)).

Explicit computation of

2

(via the

Zak transform), for

pO

.=

q,,

=

G,

leads to [2]

g(x>

=

cexz/2

(

-

1)ne-T(n+

I/2?

n

+

1/2

z

x/&

where

C

is a normalization constant.

For

g

Gaussian, as in (2.3.17), the fact that the

g,,,

do

not span

L2(R)

if

pO'qi,

>

27r, has been known for quite a

while [611, 1621. The proofs in [611, 1621 use entire function

techniques. These techniques do not work, however, for

non-Gaussian

g.

Our first table of numerical results, for Gaussian

g,

lists

pf,,

for different values

of

qo

(see Table I). It turns

out that

ph

is always very close to 27r/q,; for this reason

we have tabulated (27r/qi,.p6)- 1, rather than

p6

itself.

The difference (27/q0.p6)- 1 is largest for

q(,

=

G,

where it is about 4

X

lop3.

TABLE

I*

1

.o

6X

lo-'

1.5

3~10-~

2.0

2x

10-~

3.0

4x

3.5 2x

lo-'

4.0 8X

2.5

4X

lo-'

*The deviation,

for

g(x)=

~-'/~exp(-

x2/2),

of the esti-

mated value

ph

from the opti-

mal value

2~/9,)

(see text).

Note that

Pi

_<

27/q,. The numerical results show

therefore that in this case the estimate

pf,

is remarkably

close to the true critical value

Pi.

In fact they suggest the

conjecture that

Pi

=

27/q0, for all

qo

>

0,

in this case.

I

believe that this conjecture holds for all positive functions

g

with positive Fourier transform.

Next we list the estimates (2.3.14) and (2.3.15) on the

frame bounds for a few values of

qil,

po

<

ph.

We also

tabulate the corresponding B/A, and

r

=

(B/A

-

I

l)/(B/A

+

1). This parameter measures how snug the

frame is, i.e., how close it is to a tight frame; as explained

in Section

11-A,

this parameter is essential

if

one wants to

apply the inversion formula as indicated in Section 11-A.

We have grouped together different values of

qo,po

cor-

responding to the same value of

qo.po.

If

qo.po

=

27/k,

with

k

integer, then a different method, based on the Zak

transform, enables

us

to write explicit, exact expressions

for the frame bounds

A

and B. With

U,

defined as in

Section 11-C-la (see (2.3.Q with

A

=

qo),

one finds indeed

that, for

m

E

Z,

m

=

m'k

+

r,m', r

E

Z,

0

I

r

<

k,

(

Uzgmn

1

(

t,

s

1

=

(

Uzgm'k

+r

n

1

(

t,

s

1

-

e2rrirn/ke-2~irn

2~im's

-

e

(Uzg')(t,s)

where we have used

po

=

27r/q,, and where

g(x).

g'(

x)

=

pW,,/k

Hence

(U,g')(t,s)=(U,g)

t--s

.

(

I)

This is entirely similar to computations made in Section

11-C-la; see also [451. Consequently, as in Section 11-C-la

(see also [161, [45])

which implies

To find

A

and B, in the case where 27r/(p,.q,) is an

integer, it suffices therefore to compute

Uzg

and these

two extrema.

In Table I1 next we list the estimates, given by (2.3.141,

(2.3.15) for

A,

B, B/A and

r,

for a few values of

qo,

in

the cases

po.qo

=

~/2, 3x/4,

T,

37r/2, and 1.97. In the

cases

po'qo

=

7r/2 and

7r

we also list the exact values for

A,

B, denoted by

Aexact,

B,,,,,. For values of

po

close to

the critical value 27r/q0 (see the case

qo'po

=

1.97 in

Table I), the ratio

B/A

becomes very large, as was to be

expected. The convergence

of

the formula for

2,

mea-

sured by

r,

will be very slow. For

qo

=

2.0,

po

=

7/q0

=

~/2, the ratio

r

is already of the order of 0.2, while

qo

=

1.5,

po

=

7r/3,

qopo

=

7/2 leads to

r

=

0.025. In the

latter case a few terms will suffice to obtain an accuracy

of

is the computation of

2.

This shows that very

good frames can be obtained with lattice spacings that are

not very small.

In the two cases where the exact values of

A,

B can be

computed by other means

(qo.po

=

7/2 and

qo*po

=

71,

the estimates for

A

and B, as calculated from (2.3.14) and

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

982

IEEE

TRANSACTIONS ON

INFORMATION THEORY, VOL.

36,

NO.

5,

SEPTEMBER

1990

TABLE

I1

VALUES FOR

THE

FRAME

BOUNDS

A,

B,

THEIR

RATIO

B/A,

AND

THE

CONVERGENCE

FACTOR

r

=

(B/A

-

l)/(B/A

+

l),

FOR

THE

CASE

g(x)

=

P-'/~

exp(

-

x2/2),

FOR

DIFFERENT

VALUES

OF

q0.

po*

0.5

1.203

1.221 7.091

7.091

5.896 0.710

1.0

3.853 3.854

4.147

1.076 0.037

1.5

3.899 3.899

4.101

1.052 0.025

2.0 3.322

3.322 4.679

4.679

1.408 0.170

2.5 2.365

2.365 5.664

5.664

2.395 0.41 1

3.0

1.427 1.427

6.772 6.772

4.745 0.652

4tr'Po

=

3r/4

40

A

B

B/A

r

=(B

-

A)/(B

+

A)

1.0 1.769

3.573

2.019 0.338

1.5 2.500 2.833

1.133 0.062

2.0 2.210 3.124

1.414 0.172

2.5 1.577

3.776

2.395 0.41 1

3.0 0.951 4.515

4.745 0.652

4t)'PtI

=

r

9[)

A

Acracl

B

B,,,,,

B/A

r=(B-

A)/(B

+

A)

1.0 0.601 0.601 3.546

3.546

5.901 0.710

1.5

1.519 1.540

2.482 2.482

1.635 0.241

2.0 1.575 1.600

2.425

1.539 0.212

2.5

1.172 1.178

2.843 2.843

2.426 0.416

3.0 0.713 0.713 3.387

3.387

4.752 0.652

qtl~pt,

=

3712

411

A

B

B/A

r

=(B

-

A)/(B

+

A)

1.0

0.027

3.545 130.583

1.5

0.342

2.422 7.082

2.0 0.582 2.089

3.592

2.5 0.554 2.123

3.834

3.0 0.393

2.340 5.953

3.5 0.224

2.656

11.880

4.0 0.105 3.014

28.618

90

'Po

=

1.9r

911

A

B

B/A

0.985

0.753

0.564

0.586

0.712

0.845

0.932

close to a multiple

of

the unit operator. Consequently

g

=

U-'g

is very close to a (scaled) Gaussian. For increas-

ing

po

=

qo,

several things happen to

g.

The decrease

of

both frames bounds

A

and

B,

which reflects the decrease

in the "oversampling ratio"

27r(poqo)-',

causes the am-

plitude of

g

to increase. Moreover, the frame becomes

less and less snug (for

po

=

qo

=

(1.97r)'12,

one even has

r

>

0.91,

causing to deviate more and more from a

Gaussian. In all these examples (Figs.

4(a)-4(e)),

the

function

g

remains square integrable, however. One can

even show that it remains

C",

with fast decay. This is no

longer the case

if

po

=

qo

=

(2~)"~.

In this limiting case,

where the

g,,

no longer constitute a frame, one can still

construct

=

U-'g,

but, as previously shown, is no

longer in

L2.

This singular

g'

was first plotted by

Bastiaans

[2];

we have replotted it here in Fig.

4(f).

One

clearly sees how the regular

2,

for lower values of

po-qo,

approaches the singular limiting function as

po

=

qo

in-

creases towards

(27r)'12.

In this

case

rn(g;q,)

and

M(g;q,)

can be calculated explicitly.

One finds

ii)

The

exponential case:

We take

g(x)

=

4g;qo)

=(sinhqo)-'

M(g;q,)

=cothq,.

The function

p

cannot be written in closed analytic form.

In Table 111 we list

p;

for a few values of

qo;

we also list

again

27r/(qo.p;)-l,

which is much less close to zero

in this case. In Table

IV

we list

A,

B,

B/A

and

r=

(B/A

-

1)/(

B/A

+

1)

for several values

of

qo,

po.

Again

we have grouped together those pairs

qo,po

with the

same value of

po.

qo;

in the cases

po.

qo

=

T

/2,

po.

qo

=

7r/4

we compare the estimates with the exact values.

1.5 0.031

2.921

92.935 0.979

2.0 0.082

2.074

25.412 0.924

2.5 0.092 2.021

22.004 0.913

3.0

0.081

2.077

25.668 0.925

3.5 0.055 2.218

40.455 0.952

4.0

0.031

2.432 79.558

0.975

TABLE

111

THE ESTIMATED

VALUES

p&

AND

THEIR

DEVIATION

FROM

2r/q,,

FOR

g(x)=

e-'x'

4n

Pk

2r/(qn.p:)-

1

*Where possible

(qo.po

=

r/2,

qO,ppo

=

P)

the estimates for

A,

B

are

compared with the exact values (computed via the Zak transform; see

text)

(2.3.151,

turn out to be remarkably close to the true

values, giving deviations of at most a few percent on

A,

and less than

0.1%

on

B.

In the next example we shall

find similar orders of magnitude for the deviation of our

estimates for

A,B

with respect to the exact values. The

formulas

(2.3.14)

and

(2.3.15)

seem thus to give quite

good results, despite the rather brutal estimating methods

used.

For every one of the values of the product

qo*po

in

Table I1 we have also computed by means of the

inversion formula

(2.1.5).

These functions

g'

are plotted in

Fig.

4,

for the choice

qo

=

po.

For

po

=

qo

=

(7r/2)'I2,

we know, from Table

11,

that

the frame is snug

(r

2:

0.02

in this case), i.e., that

U

is

very

~

0.5

1

.0

1.5

2.0

2.5

3.0

3.5

4.0

5.32 1.36

2.99 1.10

2.52 0.66

2.21 0.42

1.92 0.30

1.68 0.25

1.48 0.22

1.33 0.17

In the two cases, in Table

IV,

where the exact values of

A,

B

can be computed via the Zak transform (for

qo*po

=

7r/2

and

qo*po

=

7r/4),

we see again that the estimates

for

A

and

B

given by

(2.3.14)

and

(2.3.15)

are remarkably

close to the exact values. The error on

B

is negligible,

and the error on

A

does not exceed a few percent. Note

also that frames based on the exponential used here are

much less ''snug" than Gaussian frames (compare e.g.,

the value of

r

for

qo

=

1,

po

=

~/2,

which is

0.399

in the

present case, but

0.037

for a Gaussian).

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANAI-YSIS

983

TABLE

IV

VALUES

FOR

THE

FRAME

BOUNDS

A,

B,

THEIR

RATIO

B/A,

AND THE

CONVERGENCE

FACTOR

r

=

(B/A

-

l)/(B/A

+

1).

FOR

THE

CASE

g(x)

=

exp(

-

Ixl),

FOR

DIFFERENT

VALUES

OF

q,,,

prr*

~

1.0 2.600

2.724

6.056 6.056

2.330 0.399

1.5 2.665

2.692 6.781

6.781

2.544 0.436

2.0 2.179

2.190

8.326 8.326

3.821 0.585

2.5 1.648

1.657 10.140

10.140 6.152

0.720

3.0

1.197 1.206

12.060 12.060

10.074 0.819

qo‘po

=

37/8

90

A

B

B/AQ

r

=(E

-

A)/(B

+

A)

0.5 2.014

8.873 4.405

0.630

1.0 4.203

7.339

1.746 0.272

1.5 3.724 8.872

2.382 0.409

2.0 2.938 11.068

3.767 0.580

2.5 2.204 13.514

6.133 0.720

3.0 1.597 16.080

10.068 0.819

40.Po=a/4

qo

A A,,,,,

B B,,,,,

B/A

r

=(B

-

A)/(B+

A)

1.0

6.757 6.766 10.554

10.554

1.562 0.219

1.5 5.634

5.645 13.259

13.259 2.353

0.404

2.0 4.412 4.426 16.597 16.597

3.762 0.580

2.5 3.306 3.322 20.271

20.271

6.132 0.720

3.0 2.396 2.413 24.119 24.119

10.068 0.819

*Where possible

(qo.pI,

=

n/2, ql,’po

=

a/4)

the estimates for

A,

B

are compared with the exact values (computed via the Zak transform;

see text).

2)

The Wavelet Case:

a)

Ranges for the parameters

a,,

bo-

Estimates for the

frame bounds:

In Section 11-B-lb) we construct tight

frames for arbitrary choices of

a,

>

1,

b,

>

0.

This shows

that there exists no absolute,

a

priori

limitation on

a,,

b,

-values leading to frames, unlike the Weyl-

Heisenberg case, where

po.qo

I

27 is a necessary condi-

tion (see Section 11-C-la)). This freedom in the choice of

aO,b,

is deceptive, however, because of the behavior of

wavelet frames under dilations. If the

h,,,

based on

h,

with parameters

a,,

bo,

constitute a frame, then

so

do the

hy;,,,

based on

h,(x)

=

y’I2h(yx),

with frame parame-

ters

a,,y-’b,.

This explains, at least partially, why a

frame can be constructed for

any

pair a,,b,.

To

elimi-

nate this dilational freedom, let us restrict our attention,

in the pre:ent discussion, to frames such that

llhll=

1

and

jdk

lkl-’Ih(k)l*

=

1.

Under this restriction, one might

hope again that there exists a critical curve

b$a,)

sepa-

rating the “frameable” pairs from the “nonframeable,”

with the orthogonal bases corresponding to the curve

itself. This was the situation for the Weyl-Heisenberg

case. It turns out however that this picture is not true in

the wavelet case. At the end

of

this subsection, in Theo-

rem 2.10, we establish the following counterexample. We

take

Y.

Meyer’s basic wavelet

I,/J,

and look at the

i,!~,,,~~~,

a

family of wavelets generated from

I,/J

with

a,=

2,

b,

arbitrary. For

bo=

1, these wavelets constitute an or-

thonormal basis [31]. If there existed a nice critical curve

bh(a,)

separating frameable and nonframeable values,

then we would expect that the

i,!J,,,n;h,,

would not be a

frame for

bo

>

1

(“not enough” vectors), and might be a

frame consisting of nonindependent vectors for

b,,

<

1

(“too many” vectors). It turns out, however (see Theorem

2.10), that there exists

E

>

0

such that, for all values of

6,)

in

(1

-

E,

1

+

E),

the associated

i,!J,,:b,,

constitute a basis

for

L*(R).

This baffling fact shows that the concept of

“phase space density,”

so

well-suited for Weyl-Heisen-

berg frames, is not well adapted to the wavelet situation.

For the wavelet case this is all we have to say in answer

to question 11, as formulated at the start of Section 11-C.

The following theorem addresses question 21, i.e., the

determination

for

a given function

h,

of a range

R

such

that the

h,,

are a frame for all choices

(a,,

bo)

E

R.

The

formulation of this theorem is very similar to Theorem

2.5, and

so

is its proof.

Theorem

2.7:

If

1)

m(h;a,)=

essinf

Ih(a;;,x)I*>O

(2.3.18)

Ixlr[l,a,,l

,€L

2)

M(h;a,)=

esssup

Ih(arx)l*<m

(2.3.19)

and

Ixl~[1,a,,l

rnEZ

where

P(s)=

sup

~i(a;;,x)~~i(a~x+s)

lxl€[l,a”l

rnEZ

Then there exists a

B,“

>

0

such that

Vb,

E

(0,

B,“)

:

the

h,,

associated to

h

constitute a frame,

(2.3.20)

.

(2.3.21)

a,,b,

VS

>

0

Ab,

in

[

B;,

Bi

+

S]

such that the

g,,

associated to

h,

a,,

b,,

are not a frame.

Pro08

see Appendvc

C.

0

Remarks:

1)

The conditions (2.3.181, (2.3.19) are again necessary

conditions.

If

(2.3.18)

is not satisfied, then

inf,,,2

llfll~*~,,,l(h,,,

f)I2

=

0,

which excludes

the existence of a nonzero lower frame bound. Simi-

larly (2.3.19) is necessary for the existence of a finite

upper frame bound.

2) The range

R

of “good” parameters, i.e., the set of

(a,,

bo)

such that the

h,,,

associated to

h,

a,,

bo,

constitute a frame, need not be connected. It is

possible to construct functions

h

such that, for fixed

b,,

there exist

a,,,

<

a,,*

<

for which the

h,,

associated with

h,

a,,j;

b,

constitute a frame

if

j

=

1

or 3, but do not if

j

=

2. (The construction is similar

to the one given for the Weyl-Heisenberg case. See

Remark 2, following Theorem 2.5.)

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

984

IEEE

TRANSACTIONS ON

INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

3)

Theorem

2.7

is pnly useful for choices of

h

for which

the support of

h

contains negative as well as positive

can be sharpened. The following corollary is due to Ph.

Tchamitchian.

frequencies. In some cases one prefers to work with

functions

h

with support

h

c

R,.

Functions with this

property are also called "analytic signals," because

they extend to functions analytic on a half-plane.

Theorem

2.9:

Choose

a,=

2.

Under the same condi-

tions as in Theorem

2.7,

the following estimates for the

frame bounds

A,

B

hold,

{h;,,;m,nEZ,

h+=h,

h-=h*)orof{h',"A;

m,nE

I=O

See e.g.,

[681.

The frame to be used then consists

of

Z,

A

=

1,2

h"'

=

&

re

h,

h")

=

&

im

h).

For these

frames the conclusions of Theorem

2.7

hold under

very similar conditions. The only changes to be made

concern the definitions of

m(h;

a,),

M(h;

a,)

and

B(s).

In each of these definitions, the condition

(2.3.25)

I=O

1x1

E

[l, a,]

should be replaced by

x

E

[l,~,].

As in the Weyl-Heisenberg case (Theorem

2.51,

the con-

ditions

(2.3.18)-(2.3.20)

may seem very technical. They

are however very easy to check on a computer. Good

estimates for

m(h;a,),

M(h;a,)

and

p(s)

lead again to

useful inequalities for the frame bounds

A

and

B.

-pI

-

-(2/+1)]]"*} (2.3.26)

(t

Theorem

2.8:

Under the same conditions as in Theo-

where

rem

2.7,

the following lower bound for

B,'

holds

I

Pro08

See Appendix C.

0

Note that the estimates in Theorem

2.9

use some of the

phase information contained in

fi,

which is completely

lost in the estimates in Theorem

2.8.

It is therefore to be

expected that the estimates

(2.3.23, (2.3.26)

are

,a

signifi-

cant improvement

(2.3.231, (2.3.24)

for complex

h.

This is

illustrated most dramatically by applying both pairs of

at the end of Section 11-B-lb)). For

h

=

@,

with

@

defined

by

(2.2.71,

one finds

C,l@(2"y)I2

=

1,

p(27r)

=

p(-277)

=

1/2, p(47)=p(-4~)=1/2,

and

p(k2~)=0

if

lkl23,

bn

k=l

[

(

1

(

]]"2)'

hence

c~=1[p(2~k)p(-2~k)]1/2

=

1.

Applying Theorem

2.8

we therefore find

A

2

-

1,

B

I

3.

This means that if we had only the bounds

(2.3.231,

(2.3.24)

to go by, we wouldn't be able to recognize that

the

@mn

constitute a frame. Since, for

a,

=

2

and

bo

=

1,

the

@,,,

do in fact constitute an orthonormal base, this is

a rather poor performance. Calculating

PI

we find that

>m(h;a,)

.

(2.3.22)

i

For

<

'0

<

'69

the

foilowing

estimates

for

the

frame

estimates to the basic wavelet in

y.

Meyer's basis (defined

bounds

A,

B

hold

A>-

m(h;a,)-2

p

-k

p

--k

(2.3.23)

2=

i

BI-

k=l

(2.3.24)

p,(2~k)

=

0,

for all odd

k.

Pro08

see Appendix C.

0

Remark:

The proof in Appendix

C

applies for the case

where both

R+

n

support

fi

and

iw-

n

support

fi

hav:

nonzero measure. If this is not the case, e.g., if support

h

c

R+,

and the frame considered is either

{h;,lm,n

E

Z,

h+=h,h-=h*)or{h',"~lm,(nEZ,

A=1,2,h("=&reh,

=

fi

im

h}

see Section 11-B-lb)), then the definitions

of

m(h;

a,,),

M(h;

a,),

p(s)

have to be slightly changed

(the restriction

1x1

E

[l,

a,]

is replaced by

x

E

[l,

a,]-see

Remark

3

following Theorem

2.71,

and the same formulas

(2.3.231, (2.3.24)

apply.

In most practical examples the dilation parameter

a0

is

equal to

2.

In this case the estimates

(2.3.23)

and

(2.3.24)

The estimates in Theorem

2.9

thus lead to

A

2

1,

B

I

1,

or equivalently to the optimal estimate

A

=

B

=

1.

(Note

that this automatically proves that the

@,,

constitute an

orthonormal basis, since

11@,,,11

=

ll@ll=

1.

We showed in

Section 11-A that a tight frame with frame constant

1,

consisting of normalized vectors, necessarily is an or-

thonormal basis.) Since the phase factor in the definition

of

Y.

Meyer's basic wavelet

(2.2.7)

is essential for the

@,,

to constitute an orthonormal basis (see e.g.,

[311),

it is

natural that the phase-dependent estimates

(2.3.25),

(2.3.26)

perform much better than the phase-independent

estimates

(2.3.231, (2.3.24)

in this case. Using Theorem

2.9

one can prove the result we just announced, i.e., that

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

985

the wavelets

+hrn,,,

associated with

Y.

Meyer’s

$,

and with

a,

=

2,

b,,

arbitrary, still constitute a basis for

b,

#

1,

16,)

-

11

<

E,

for some

E

>

0. The following Theorem was

proved in collaboration with Ph. Tchamitchian.

Theorem

2.10:

Let

$

be the function defined by (2.2.7).

Then there exists

E

>

0

such that the

$rnn;bl,,

constitute a basis for

L2(R),

for any choice

bo

E

(1

-

E,

1

+

E).

Proofi

See Appendix C.

0

This result is quite surprising: it shows, as pointed out at

the start of Section 11-C-2, that it is not always safe to

apply “phase space density intuition” to families of

wavelets.

Remark:

It follows from the proof that

E

can be esti-

mated explicitly, from computations

of

the frame bounds

A,

B,

as given by (2.3.25), (2.3.26) on the one hand, and of

Corollary

2.11:

Let

h’;

.

.,

hN-’

be

N

functions satis-

fying the conditions (2.3.181, (2.3.19), and (2.3.20). Define

m(h”;..,hN-l;a,)=

essinf

CI~J(~;;~X)I~

N-I

IxlE[I,a,,l

j=()

m

(2.3.27)

N-1

~(h”;..,h~-’;a,)=

esssup

c~ij(a;;’x)~’

p’(s)=

sup

IAl(a;;x)l/6’(a;;’x+s)I.

Ixl~[l,a~J

j=o

m

(2.3.28)

lxlE[1,a,,l

tntz

(2.3.29)

Choose

b,

such that

N-l

m

1

/2

j=O

k=l

<

m(h”;

. .

,

hN-l;

a,).

Then the

(h;,,;

rn,

n

E

Z,

j

=

0,.

. .

,

N

-

1)

constitute a

frame. The following estimates for the frame bounds

A

and

B

hold,

on the other hand. This estimate for

E

depends, of course,

on the choice for the function

v

(see (2.2.7)). For the (non

C”)

choice

4x1

=

x

if

0

I

x

<1,

v(x)

=

0 otherwise, one

finds

E

>

0.02. The

$,,,n,bll

remain a frame for

b,

I

1.08 in

this case.

In many practical examples

fi

decays very fast, and is

real. In those cases the differences between estimates

using

p

(i.e., (2.3.231, (2.3.24)) or

pl,

(i.e., (2.3.2.51, (2.3.26))

are very small, and myh less dramatic then for

Y.

Meyer’s

wavelet

$.

In fact,

if

h

is positive (e.g., the Mexican hat

function, the 8th derivative of the Gaussian, the modu-

lated Gaussian,

.

s

:

see the next subsection) the esti-

mates using

p

perform better than those using

PI,

as can

easily be checked directly by the formulas (2.3.231, (2.3.241,

and (2.3.29, (2.3.26).

As already mentioned above, most practical applica-

tions use

a,

=

2. This choice makes numerical computa-

tions much easier since

it

means that the translation steps

b,,.2rn (see Fig.

l(b)),

for two different frequency levels

m,

>

m2,

are multiples of each other. It also makes the

different frequency levels correspond to “octaves.” On

the other hand one likes to use fyctions

h

with fairly

concentrated Fourier transforms

h,

correspondinng to a

good frequency resolution. This means that Crnlh(2”x)12

is bound to have rather large oscillations; since then

m(h;2)

is

much smaller than M(h;2), this leads to high,

and therefore unpleasant values of

B/A.

This can be

avoided by the use ocseveral functions

h’,

chosen

so

that

the minima of ACmlhJ(2rnx)12 are compensated by the

maxima of

C,,,lh”(2’”~)1~,

for some

j’# j.

This is made

explicit by the following corollary of Theorem 2.7.

.[PI(

?k)pJ(

-

Ek)]”’]

(2.3.30)

N-1

m

j=O

k=l

Po

*[@I(

$k)pl(

-gk)]”2].

(2.3.31)

Proofi

The proof is a simple variant on the proof of

Theorem 2.8.

0

In the special case where

a,,=

2, one can,

of

course,

replace

p’

in (2.3.301, (2.3.31) by

pi,

with

pi

defined as in

Theorem 2.8, for

j

=

0;

.

.,

N

-

1.

Then the sums over

k

#

0 also have to be replaced by sums over only odd

k.

The number

N

of

functions used is called the number

of

“voices” per octave [28]. In numerical calculations

N

=

4 seems to be a satisfactory choice.

In practice one often chooses the

h”; .

.,

hN-l

to be

dilated versions of one function

h,

i.e.,

hJ(

x)

=

2-j/Nh(2-’/Nx),

j

=

0;

. .

,N

-

1.

(2.3.32)

The phase space lattice corresponding to the

{hAn;

m,n

E

Z,

j

=

0;

.

.,

N

-

1)

is the superposition of

N

lattices of

the type depicted in Fig. l(b), shifted with respect to each

other in frequency. Fig.

5

shows such a lattice, for the

case

N

=

4, and for

a,

=

2.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

986

IEEE

TRANSACTIONS

ON

INFORMATION

THEORY, vol..

36,

NO.

5,

SEPTEMBER

1990

.......

........

......

........

*

-

*

........

......

.

ko

k::::::

‘I’

i

1

f

Remark:

Note that the

h’,

constructed by dilations from

one function

h

as in (2.3.321, do not have the same

,!,*-normalization,

IlhJllL~

=

2-J/2N

IlhllL2.

This change in

normalization compensates for the fact that the phase

space lattice in Fig.

5

is “denser” than the corresponding

lattice (see e.g., Fig. l(b)) would be for the same basic

wavelet

h,

but with

a,

=

2’”, and with only one function

(namely

h1

per dilation step (instead of

N,

as in Fig.

5).

b)

Examples:

We illustrate the different bounds with

several examples. In practice, it is by far preferable to use

a,

=

2,

rather than noninteger values. We have therefore,

in all our examples, restricted ourselves to

a,

=

2, and

introduced several voices (see Corollary 2.11). The differ-

ent voice-functions

hJ

are always obtained, in these exam-

ples, by dilation

of

one given function

h

(see (2.3.32)).

i)

One cycle

of

the sine-function:

In this case we take

10,

otherwise

The Fourier transform of

h

is given by

fi

sinyr

h(

y>

=

-i-

T

1-y2’

TABLE

V-A

FRAME

BOUNDS

FOR

WAVELET

FRAMES*

N=l N=2

-

~

bo/r

A B B/A

bo/r

A

B B/A

~ ~

0.25 4.038 8.409

0.50

1.838 4.386

0.75 1.412 3.007

1.00

0.585

2.527

1.25 0.337 2.152

N=3

-

bn/r

A

B

~

2.082 0.25 11.950 16.294

2.387

0.50

5.711 8.411

2.634 0.75 3.629 5.785

4.323 1.00 2.410 4.651

6.380 1.25 1.709 3.939

1.50 0.999 3.708

1.75 0.556 3.479

2.00 0.202

3.328

N=4

-

B/A

bn/r

A B

1.364

1.473

1.594

1.930

2.305

3.713

6.259

16.473

0.25 20.035

0.50

9.655

0.75 6.185

1.00 4.230

1.25 3.050

1.50 2.033

1.75 1.313

2.00 0.736

24.331

12.528

8.603

6.861

5.823

5.361

5.025

4.810

1.214 0.25

1.298

0.50

1.391 0.75

1.622

1

.oo

1.909 1.25

2.637

1

SO

3.828 1.75

6.539 2.00

27.986

13.598

8.687

6.042

4.431

3.076

2.031

1.261

32.500

16.645

11.475

9.080

7.666

7.005

6.610

6.300

1.161

1.224

1.321

1.503

1.730

2.278

3.255

4.998

*Based

on

the function

h(x)

=

{

r-II2

sin

x

1x1

I

r

The dilation parameter

a,

=

2 in all cases; N

is

the number of “voices”

(see text).

0,

otherwise

ii)

The Mexican hat:

The Mexican-hat function is the

second derivative of the Gaussian (up to a sign),

2

h( x)

=

-r-’/4(

1

-

x2)e-X2/2

6

2

h(

y)

=

-r-1/4y2e-~2/2.

The graph

of

h

looks

a bit like a transverse section

o,f

a

Mexican hat (see Fig. 2(b)), whence the name. Since

h

is

positive, the formulas using

p

rather than

PI

are more

effective here. The same will be true in

our

next exam-

ples. Table

V-B

lists the estimates for the frame bounds

A,B

and their ratio, for a few values of the translation

parameter

bo,

and of

N,

the number of voices.

iii) The eighth deriuatiue

of

the Gaussian:

Functions

like the Mexican hat and higher order derivatives of the

Gaussian are useful in applications of the wavelet trans-

form

to

edge detection (see, e.g., [27]). Table

V-C

lists the

estimates for the frame bounds

A,B

for wavelets based

on the eighth derivative of the Gaussian,

-

405x2

+

90)

1

/2

T-1/4

x

-y2/2

Since this is an oscillating function, one suspects that

the formulas analogous to (2.3.301, (2.3.311, but using

PI

~(y)=(z)

ye

.

rather than

p,

will perform better than the P-formulas.

This turns out to be true. Table

V-A

lists the estimates

for the frame bounds

A,B

and their ratio, for a few

values of

b,,

and of

N,

the number of voices.

This is a typical example of a function where, with

a,,

=

2

fixed, the introduction of several voices is necessary. For

N=

1

(i.e., only one voice, corresponding to the phase

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES:

THE

WAVELET

TRANSFORM,

TIME-FREQUENCY

LOCALIZATION

AND

SIGNAL ANALYSIS

987

TABLE V-B

FRAME BOUNDS

FOR

WAVELET FRAMES*

N=l N=2

bo

A

B

B/A

b,

A

B

B/A

-

0.25 13.091 14.183 1.083

0.50 6.546

7.092 1.083

0.75 4.364

4.728 1.083

1.00 3.223 3.596

1.116

1.25

2.001 3.454

1.726

1.50 0.325

4.221 12.986

N=3

-

bo

A

B

B/A

~~

0.25 27.273

27.278

0.50

13.637 13.639

0.75 9.091

9.093

1.00

6.768 6.870

1.25 4.834 6.077

1.50 2.609 6.483

1.75 0.517

7.276

N=4

bo

A B

-

1.0002

1.015

1.257

2.485

14.061

B/A

0.25 40.914

40.914 1.0000 0.25 54.552

54.552 1.0000

0.50

20.457

20.457 1.OOOO 0.50

27.276 27.276 1.0000

0.75 13.638

13.638 1.0000 0.75 18.184

18.184

1.0000

1.00

10.178

10.279

1.010

1.00

13.586 13.690 1.007

1.25 7.530

8.835 1.173 1.25

10.205 11.616

1.138

1.50

4.629

9.009 1.947

1.50

6.594

11.590 1.758

1.75 1.747

9.942 5.691 1.75 2.928 12.659 4.324

*Based on the Mexican hat function

h(x)

=

2/fi.rr-1/4(1

-

x2)e-xz/2.

The dilation parameter

a.

=

2

in all cases;

N

is the number

of

voices

(see text).

TABLE

V-C

FRAME BOUNDS

FOR

WAVELET FRAMES*

0.125

0.250

0.375

0.500

0.625

0.750

0.875

b0

25.515

26.569

12.758

13.285

8.505

8.856

6.379

6.642

5.101

5.316

3.995 4.686

1.669

5.772

N=3

-

A B

1.041

1.042

1.173

3.459

B/A

0.125

0.250

0.375

0.500

0.625

0.750

0.875

1

.000

bn

39.054

19.527

13.018

9.764

7.808

6.251

3.563

0.163

A

39.073

19.536

13.024

9.768

7.817

6.770

7.598

9.603

N=4

-

B

1.0005

1.001

1.083

2.132

58.929

B/A

~

0.125

0.250

0.375

0.500

0.625

0.750

0.875

1.000

52.085

26.042

17.362

13.022

10.414

8.420

5.313

1.127

52.085

26.042

17.362

13.022

10.420

8.941

9.568

1 1.894

1

.oooo

1

.om0

1

.OoOo

1

.oooo

1.0005

1.062

1.801

10.550

*Based on the

8th

derivative of the Gaussian,

(

2;;;!

)1'2

h(x)=

-

.~-"~(x~-282~ +210x4 -405~' +90)e-XZ/2.

The dilation parameter

a,,

=

2

in

all

cases;

N

is the

number

of

voices.

space lattice in Fig. l(b)) one finds that M(k;2)/m(k;2)

is equal to 3.385. This Feans tha! the ratio

B/A,

which is

bounded below by M(h; 2)/ m(h; 21, is pretty large, with

N

=

1,

even for very small values of

bo.

As

soon as more

voices are introduced, the ratio M/m becomes much

smaller, and snug frames can be constructed, for appro-

priate choices of

bo.

We have restricted ourselves, in

Table Vc, to the choices

N

=

2,3,4, excluding

N

=

1.

iv)

The modulated Gaussian: In this case we take

h(.) =T-1/4(e-lkx-

e-k2/2)e-x2/2

&(

y)

=

T-l/4(

e-(~-k)2/2

-

e-k2/2e-~z/2

)

where

k

=

~(2/ln2)'/*.

Tht subtraction term in the definition of

h,L

ensures

that h(0)

=

0;

for the value of

k

chosen here, this term is

negligible in practice. The value

of

k

has been fixed

so

that the ratio between the highest and the second highest

local maxima

of

Re h is approximately 1/2. This wavelet

is exactly the wavelet used by

J.

Morlet in his numerical

computations [25], [26]. If only real signals

f

are decom-

posed and reconstructed, by means of the (hmn,f), then

the complex wavelet

h

consists really

of

two

wavelets,

Re

h

and Im h. In this case the frame bounds for real

signals can be rewritten

as

with

and

1

p,(

s)

=

-

sup

(k(

atx)

+

€L(

-

a;;.)

1

4xm

.Ik(ab"x

+

s)

+

€k(

-

a;;..

-

s)

1.

Note that

fi

is almost completely concentrated on the

positive frequency kalf line; neglecting terms with nega-

tive arguments for

h

in the previousjormulas leads back

to the frame bounds for support hcR,. In the first

reconstructions with this wavelet, before even the connec-

tion with continuously labelled affine coherent states was

made (see Sections I-E,I-F), a formula similar to (2.1.7)

was used. This reconstruction formula turned out to be

extremely precise. Our calculations of frame bounds show

why. For

N=

4,

bo

=

1, for instance, which are choices

that do correspond to values used in practice (in fact, [251

uses even higher values of

N,

and smaller values

of

bo),

we find

B/A

=

1.0008. Hence

r

=

(B

-

A)/(B

+

A)

=

0.04%, which explains why (2.1.7) is such a good approxi-

mation to the true reconstruction formula.

As

in the previous example, the ratio M/m is rather

large for

N

=

1, and we have computed the frame bounds

only for

N

=

2,3, and 4. They are tabulated in Table V-D.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

988

TABLE

V-D

FRAME

BOUNDS

FOR

WAVELET

FRAMES*

0.5 6.019 7.820

1.299

1

.o

3.009

3.910 1.230

1.5 1.944

2.669 1.373

2.0 1.173

2.287 1.950

2.5 0.486

2.282 4.693

N=3

b

I,

A B B/A

~

0.5

10.295

10.467

1.017

1

.o

5.147 5.234

1.017

1.5 3.366

3.555 1.056

2.0 2.188

3.002 1.372

2.5 1.175

2.977 2.534

3.0 0.320

3.141 9.824

N=4

-

b”

A B B/A

0.5 13.837

13.846 1.0006

1

.o

6.918

6.923 1.0008

1.5 4.540

4.688 1.032

2.0 3.013 3.910

1.297

2.5 1.708

3.829 2.242

3.0 0.597 4.017

6.732

*Based on the modulated Gaussian,

h(x)=T-1/4(e-~kx

-

e-k2/2)e-xz/Z

with

k

=

~(2/ln2)’/~.

The dilation constant

a,,

=

2 in

all

cases; N is the

number

of

voices.

Remark:

The tables show that extremely snug frames

can be obtained for quite reasonable phase space lattices

(i.e.,

N

not too large,

bo

not too small). Note, however,

that even when

B/A

s

not very close to

1,

the frame may

still be useful.

For

B/A

=

1.5,

e.g., the convergence fac-

tor

r

=

(B

-

A)/(B

+

A)

is still of the order of

0.2;

while

this is insufficient to permit the use

of

the approximation

formula

(2.1.71,

it does mean that only a few iterations

will suffice for the computation

of

the

(h,,)“

up to e.g.,

leading, again, to a very accurate reconstruction

formula.

D.

Frames

in

Other Spaces than

L2(R)

The results in this section are more technical and

specialized than those in the preceding sections. The

reader who is mostly interested in ,!,’-results can safely

omit reading this section and go to Section 111, where we

again discuss L2-estimates.

I)

Motivation:

Why

Other Spaces

than

L2(R)?:

So

far,

we have restricted ourselves to studying frames in

L’(R1.

The preceding section was mainly concerned with the

formulation of conditions under which the short-time

Fourier expansions (Weyl-Heisenberg case) or the wavelet

expansions (affine case) would converge with respect to

the L2-norm. As explained in the introduction, both types

of expansions are used in the analysis, e.g., of time-depen-

dent signals. For such signals

f(t>,

the square of the

L2-norm,

j:,dtlf(t)12,

is a natural quantity, often called

IEEE TRANSACTIONS

ON

INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

the “energy”

of

the signal in electrical engineering litera-

ture. It is therefore customary to require L2-convergence

for series representations of these signals.

This does not mean, however, that convergence in

other topologies is not important.

For

example, conver-

gence in

L

P(R)-spaces,

with

p

f

2,

where the coefficients are weighted in a way

different from

L2(R),

would certainly indicate that the

series is more “robust” than

if

it converged in

L2(R)

alone. On the other hand,

if

the signals themselves have

some regularity (consider, e.g., the case where not only

f

but also its first

k

derivatives are

in

L’(R)),

then one

would wish that the partial sums of the series represent-

ing

f

share that regularity, and that the convergence

respects this (in the previous example, this would mean

L2-convergence also for the first

k

derivatives). It would

therefore be interesting to have convergence in the

Sobolev spaces

for at least some

s

>

0.

In the two subsections following this one, we shall show

that for suitably chosen

g

or

h,

and appropriate parame-

ters

p0,p0

or a,,b,, the resulting frames are frames in

&(RI,

at least for some strip

Is1

<

s~,.

In the remainder of

this subsection we give some examples illustrating “what

can go wrong.” The examples given here all pertain to the

wavelet case.

I

want to thank

Y.

Meyer and Ph.

Tchamitchian for having pointed them out to me.

If the

h,,

(h,,(x)

=

a;m/2h(a;mx

-

nb,))

constitute a

frame in

L2(R),

then, as shown in Section 11-A, there

exists a dual frame

{(hm,)-;

rn,

n

E

Z}

such that, for all

f

in

L’W,

f=

C

(hrnn)-(hrnn,f)

(2.4.1)

where the series converges in

L’(R).

If the frame is not

tight, then the

(hm,)-

are not multiples of the

h,,,

and

in general they will not be generated by dilations and

translations of a single function (see Section 11-A).

There are several ways in which

(2.4.1)

may fail

to

extend to

Lp(R),

with

p

#

2,

or to

&(R),

with

s

#

0.

One

possibility is that the coefficients

(h,,,f)

are not well

defined for all

f

in the space under consideration, i.e.,

that

h

does not belong to the dual

of

this space. This is

not really a problem:

it

is enough to impose some regular-

ity and/or decay conditions on

h

to avoid this. Something

much more pernicious may happen, however. It is possi-

ble that even though

h

is a “nice” function, the elements

(/I,,)-

of the dual frame are not,

so

that

(2.4.1)

fails. The

examples we shall give here illustrate this.

The first example is due to

P.-G.

LemariC. It was

communicated to me by

Y.

Meyer. Let

4

be

Y.

Meyer’s

wavelet, as

As

already mentioned, the

$,,(XI

=

m,n

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

989

2-m/2 JI(2-”x

-

n)

constitute an unconditional basis for

many function spaces, including all the

Lp(R),

1

<

p

<

W.

The wavelet coefficients

(JI,,,

f)

can be used to charac-

terize these spaces and their duals [311. In particular,

LP-spaces are characterized as follows: for any function

f

one has the equivalence

ft~p(~)-[

c

2-mI(*mn,f>12Xmn ELP(R)

(2.4.2)

where

xmn

is the indicator function

of

the interval

I,,

=

[2mn, 2”(n

+

1)).

The basic wavelet in Lemarik’s construc-

tion is the following perturbation

of

JI:

h(x)

=

JI(

x)

+

&Tr~1(2x).

This function

h

is clearly in

C”,

and has fast decay at

W.

We use the same dilation and translation parameters as

for

Y.

Meyer’s basis, i.e.,

h,,(x)

=

2-m/2h(2-mx

-

n).

Then

h,,

=

JI,,

-

rJIm-12n

=

(1

-

rU)t+b,,,,, where

U

is the

partial isometry defined by

U+,,

=

JIm-12n.

For

Irl

<

1,

the operator

(1

-

rU) is one-to-one and onto, which means

that the

h,,

still constitute a basis for

L2(W

if Irl

<

1.

The dual frame

(hmn)-

is given by

(hmn)-

=

[(l- rU)(1- r*U*)]

-‘hmn

m,n

Ill2

=

(1-

r*U*)-’+m,

=

r*kU*kJImn (2.4.3)

where

U

*$,

2n

+

=

0,

and

U

*JI,

2n

=

JI,

+

n.

In particular

m

k=O

m

(hOO)A

=

r*k$-kO*

j=O

It turns out that if

Irl>

l/a, this function does not

belong to

Lp(R)

for large

p,

as shown by the following

argument. If we apply (2.4.2) to

(h,)“,

we find

If Irl

>

l/&T,

this shows that

(h,)“

4

Lp(R)

for all

p

>

21n2/[ln2+2ln 11-13. This implies that, even though the

h,,

themselves are

C”

functions with fast decay, and

constitute

a

frame for

L2(R)

(with

A

=(l-

lr12)’/2,

B

=

(1

+

lr12)1/2), the frame expansion (2.4.1) does not extend

to all LP(R)-spaces,

1

<

p

<CO,

if IrI

>

1/a.

Note that, in the example, the

(h,,)“

are the only

functions in the dual frame causing problems. For

n

#

0,

only a finite number

of

terms in the series (2.4.3) con-

tribute, and

(h,,,)-

is still infinitely differentiable and

decaying rapidly. This might lead one to believe that the

problems are caused

by

the fact that the

(h,J

are not

given, in general, by dilations and translations

of

a single

function

h.

It is true, also, that this phenomenon

(h

E

4,

and some

(h,,)”

4

Lp) does not occur for the tight

frames constructed in Section 11-B-2b). For these frames,

results analogous to those for

Y.

Meyer’s basis hold, and

the expansions

f=

A-’

C

hmn(hmn,f)

m,n

are valid, and converge, in particular, for all LP-spaces

(1

<

p

<

w)

and all

<(R).

Nevertheless, there exist (non-

tight) frames for which the

(h,,)“

happen to be dilations

and translations

of

a single functicn

h,

and where, as in

our first example,

h

is “nice” and

h

is not, causing (2.4.1)

to fail in at least some function spaces. Our second

example illustrates this; it is a special case of a construc-

tion made by Ph. Tchamitchian

[353.

In [35], Ph. Tchamitchian constructs functions

u,

r

such

that the dyadic (i.e., ao=2,

bo

=1)

lattices

of

wavelets

generated by

u

and

T

constitute biorthogonal bases for

L~(R),

i.e.,

C

Umn(rmn,

.>

=

(2.4.4)

m,n

where the sum converges strongly in

L2(R>,

and with

The details

of

this construction, together with proofs and

applications, are given in [35b]. It is possible to choose

both

u

and

T

with compact support. One such example is

the following (see [35b]):

U,,(X)=

2-m/2U(2-mX

-

n),

T,,(X)=

2-m/2T(2-mX

-

n).

cos

-

+

-

cos

-

2 16 2 16 2

19

y1

or

1

4

dx)

=

-6

and

‘

0,

Xl-1

l/8,

-1<x<O

-1, O_(x<1/2

1,

1/2<XS1

-1/8, 1~x12

\

0,

x22

where

P(u)

=

3u2

-

2u3. Since P(cos

y)

=

1

+

O(y4),

the

infinite product in the definition of

7^

is well defined. One

finds that

8

is entire and of exponential type, implying

that

T

has compact support. Moreover, since

P(u)

1

u2

on

[O,

11,

m

~~(Y)~SIYI~

c0s4[2-j~/4]

j=

1

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

990

IEEE

TRANSA~IONS

ON

INFORMATION

THEORY, VOL.

36,

NO.

5,

SEPTEMBER

1990

Using this decay

of

i,

the compactness

of

support

7,

and

/&T(x)=

?(O)=

0,

one can easily prove that

~m,fl~(~,~m,,)l

<m.

The decay properties

of

G

are rather

weak, but one can use

/&

a(x)

=

0,

the compactness of

support

U

and the fact that

U

is piecewise constant in an

easy proof

of

Cm,nl(~,~,,)I

<m.

This implies that, for all

sequences

(C,,J,,~

E

in

L2(Z),

m,n

Together with

(2.4.4)

(for the proof of which we refer to

[35b]), this implies that the

U,,

and the

T,,

both consti-

tute frames. Moreover (see

[35]),

both the

U,,,

and the

T,,

constitute bases in

L2(R).

It is now easy to construct the example previously

announced. Take

h(x)

=

7(x).

Then

h

is of compact sup-

port, and

h

belong to

2?5/2-e(R),

for all

E

>

0,

because of

(2.4.5).

Since the

h,,(x)

=

2-m/2h(2-mx

-

n)

constitute a

frame, we can construct the dual frame,

(h,,,)“.

Since the

h,,

are linearly independent, however, and because of

(2.4.4),

we find

(h,,,)“

=

U,,,.

Since

(T

E

&(RI

only

if

s

<

1/2-

E,

we see that

all

the functions in the dual

frame are much less “nice” than those in the original

frame; in particular, they are discontinuous, while

h

itself,

together with its first derivative, is continuous.

2)

Weyl- Heisenberg Frames

in

Sobolev Spaces:

The ex-

amples in the preceding subsection show that one must be

wary when trying to generalize frames, and the associated

expansions, to other function spaces than

L2(R).

One can

however apply the techniques used in Section 11-C to

extend the notion of frame to a “strip” of Sobolev spaces

&,

with

Is1

<

so.

Proposition

2.11:

Define (as in Section 11-C-1)

p,’(

y)

=

sup

(1

+

x’)

Ts’2[

1

+

(x

+

y)’]

+s/2

X

If

c

k#O

then the operator

U,

U=

C

grnn(grnn9

.>

m,n

is bounded, with a bounded inverse, on both

x-,.

In particular, for all

fl

E

&,

f2

E

X,,

and

A,llflll,

I

Il~flllS

I

Bsllfllls

(2.4.7)

A,llf’ll-s

I

Irnf’ll-s

I

~,llf’Il-~

(2.4.8)

where

(

2.4.9)

and

k#O

(2.4.10)

Pro08

We shall show that, for all

f

E

4,

A,llfll,llfll-,

I

(f,Uf)

I

~,llfll,llfll-,.

(2.4.11)

Here, as before, we use the notation

(

,

)

for the duality

extending the L2-inner product,

With respect to

(

,

),

the spaces

&

and

A?-,

are each

other’s dual. On the other hand

U

is symmetric with

respect to

(

,

).

Since

&

is dense in

2?-,,

it follows

therefore from the upper bound in

(2.4.11)

that

U

is

bounded on both

.&

and

A??,,

with norm smaller than

B,.

Similarly the lower bound in

(2.4.11)

implies that, for

all

fl

E

&,

f2

E

S-,,

Il~flIls

2

Asllfllls,

and

lDf2Il-,

2

A,llf21I-,.

Again using the symmetry of

U

with respect to

(

,

)

one easily checks that this implies that

U

is invert-

ible, with a bounded inverse with norm smaller than

A,-’,

both on

&

and

A?-,.

It remains to prove

(2.4.11).

This is done along the

same lines as in Section 11-C.

f(~)*f

x

+

-k

i

:I

2T

40

=

-

/&

[

(1

+

xy21

f(

x)

I]

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

99

1

DAUBECHIES: THE WAVELET

TRANSFORM,

TIME-FREQUENCY

LOCALIZATION

AND SIGNAL

ANALYSIS

with

The bounds (2.4.11) then follow immediately.

I3

Remarks:

1) If the conditions of Proposition 2.11 are satisfied,

then, since

U

is invertible, and has bounded inverse

on

&,

we have

6mn

=U-’gmn

E

&

and, for all

f

E

3,

f=

C

irnn(gmn,f)

m,n

where the series converges in

&:

the frame expan-

sion holds on

&.

2) If

U

is a bounded and invertible operator on both

&

and

A?,,

then, by standard (highly nontrivial)

interpolation theorems (see e.g., Section IX-4 in

[64]), it is automatically bounded and invertible on

any

&,

with

ls‘l

is.

Proposition 2.11 gives thus a

sufficient condition for the frame expansion formula

to hold on a “strip” of Sobolev spaces. To obtain a

wide “strip,” for fixed

po,

it is clear from (2.4.6) that

we have to choose

qo

sufficiently small. Typically,

we would expect the critical value

q,C(s)

(the value of

qo

for which equality occurs in (2.4.6)) to be a

decreasing function of

s.

Note that one needs to

impose a decay condition on

p’(s>,

similar to

(2.3.131, to ensure the existence of

q,C(s).

3) Since

C,

E

,12(x

+

mpJI

IB(x

+

mp,

+

y)l is periodic

in

x,

with period

p,,

and since [1+(x

+

y)’]/

(1+x2)

has its maximum, resp. minimum, at

x=

-

y

/2

sgn (y)dw, it suffices, for numerical

computation of

P”(y),

to take the supremum over

values of

x

in an interval of length

po

around

-

y/2+sgn(y)\/l+y2/4.

Example:

For

g(x)=

r-‘l4

exp(- x2/2), Table VI-A

gives the values of

A,

and

B,

for a few values of

s,

for

po

=

r/2,

qo

=

1. Table VI-B shows how

q,C(s)

changes

with

s,

for fixed

po

=

r/2.

TABLE VI-A

FRAME BOUNDS*

S

A,

B, B,

/A,

0.0

3.853

4.147 1.076

1.0 3.852 4.148 1.077

2.0 3.849

4.151 1.079

3.0 3.836

4.164 1.086

4.0 3.787 4.213 1.112

5.0

3.600 4.400 1.222

6.0 2.865

5.135 1.793

*In the Sobolev spaces

for Weyl-Heis-

enberg frames based on the Gaussian

g(x)=

~r’/~

exp(-

x2/2),

with

p,,

=

~/2,

9,,

=

1.0,

for

changing values

of

s.

For

s

=

7,

our estimate for

A,

becomes negative: the frame breaks down.

TABLE VI-B*

0.0

3.99

1

.o

2.28

2.0 1.72

3.0 1.42

4.0 1.24

5.0 1.13

6.0 1.06

7.0 0.99

*The critical value

4$s)

for the

translation parameter

qo,

as

a

function

of

the index

s

of the

Sobolev space

in

which the frame is

consdered. Values of

qo

smaller

than

q$s)

lead

to

a frame in

4

and

Z,.

The basic function here

is g(x)=Tr’/4exp(-x2/2);

po=

rr/2

is fixed.

3)

Wavelet Frames in Sobolev Spaces:

Since the tech-

niques used for proving frame bounds in

L2(R)

were

essentially the same for the wavelet case as for the

Weyl-Heisenberg case, it is not surprising that we can

prove the following proposition.

Proposition

2.12:

Define (as in Theorem

2.7)

m(h;a,)

=

inf

~A(n;x)

12,

M(

h;

a,)

=

sup

I

i(

ay.)

12.

mcZ

X

m6L

Assume that

m(h;

a,)

>

0,

M(h;

a,)

<

m.

Define, for

s

2

0,

P’(

y)

=

sup (1

+

x’)

Ts/2

I

&(

a;;.)

I

(&I

ayx

+

y)

I

X

mtL

If

c

[

p:

(2k)p;

(-

Z-k)]’”

<

m(h;a,)

(2.4.12)

k+O

then the operator

U,

is bounded, with a bounded inverse, on both

&

and

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

992

IEEE TRANSACTIONS

ON

INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

Z-,.

In particular, for all

fl

E

e,

f2

E

2-,,

TABLE

VI1

FRAME

BOUNDS*

A,llflll,

IDflIlS

I

B,llfills

(2.4.13)

b,,

=

1.0

b,,

=

1.25

s

A, B, B,/A,

s

A, B,

4/A,

Asllf211-,

I

lDJf2ll-s

I

~,llf2ll-s

(2.4.14)

0.00 3.223 3.596 1.116

0.00

2.001 3.454 1726

where

0.25 3.223 3.596 1.116 0.25 1.995 3.460 1.734

0.50 3.222 3.597 1.116 0.50 1.985 3.470 1.748

0.75 3.221 3.597 1.117 0.75 1.971 3.484 1.768

1.00 3.220 3.599 1.118 1.00 1.953 3.502 1.793

m(h;a,)-

P:

-k

p,-

--k

1.25 1.926 3.529 1.832

1.50 3.216 3.602 1.120

1.50

1.877 3.578 1.906

1.25 3.218 3.600 1.119

1.75 3.214 3.605 1.122 1.75 1.794 3.661 2.041

k#O

[

(

)

(

2

)]‘I2]

kzO

[

(

’bi:

)

(

’bi:

)I

”4

In

the Sobolev spaces

<

for

wavelet frames based on

the

M(h;a,)-

P:

-k

p,-

--k

.

Mexican hat function

h(x)

=

23-‘/’~-’/~(1-

x’)exp(-

x2/2),

Po

with

a,

=

2.0,

b,,

=

1.0

and

1.25

for

changing values

of

s.

Proofi

The proof is entirely analogous to the proof of

Example:

Table VI1 gives

A,

and

B,,

for a few values

of

s,

for the Mexican hat function

h(x)

=

2/fi~-‘/~(l-

Proposition

2.11.

I.

Remarks:

~~)e’-~’/~,

for

a,

=

2.0,

and for

b,

=

1.0

and

1.25.

If

U

is bounded, with a bounded inverse,

on

e,

then

(h,,)“

=T-’h,,

E

f

=

C

(hmn)“(hmn,f)

(2.4.15)

and, for all

f

E

e,

m,n

where the series converges in

&.

This means that

the phenomenon illustrated by the examples in Sec-

tion 11-D-1 cannot happen, at least in

&,

if

h

satisfies the conditions in Proposition

2.12.

By interpolation (see e.g., Section IX-4 in

[64]),

one

finds that if

(2.4.13), (2.4.14)

hold in

&,

2-,,

respectively, then

U

is bounded, with a bounded

inverse, on all

&,

with

Is’I

I

s.

Under the condi-

tions in Proposition

2.12,

the frame expansion

(2.4.15)

is therefore valid in all

&,

with

Is’I

I

s.

Typically (as in the Weyl-Heisenberg case), we ex-

pect that, for fixed

a,,

the critical value

bG(s)

(i.e.,

the value of

b,

for which equality holds in

(2.4.12))

decreases with

s.

It is a remarkable fact that for

Y.

Meyer’s basis, the wavelet expansion is valid in

e,

for all

s

E

R,

for

a,

=

2,

and for

Jijred

bo

=

1.

Some-

thing similar is true for the tight frames constructed

in Section

11-B-2b).

However, for general functions

h,

leading to nontight frames, we rather expect

b$s)

to decrease with

s.

For

a given function

h,

the strip of Sobolev spaces

for which the

h,,

constitute a frame, i.e., the possi-

ble values of

s

for which

(2.4.131, (2.4.14)

holds, is

!onstrained by the behavior of

6

around zero. If

h(x)

=

O(xO)

for

x

+

0,

then clearly (see the defini-

tion

of

p:)

(y)

2

C[

inf

~i;(y

+

u>lly

+

This diverges for

s

2

cy.

am(a-s)

Id

5

arM

m

=

--?o

111. PHASE

SPACE

LOCALtZATION

Let us recall the intuition, already mentioned in the

introduction, which leads us to expect the phase space

localization results we shall give here.

Both the Weyl-Heisenberg coherent states and the

wavelets can be used to give a representation in the

time-frequency plane of time-dependent signals, provided

the basic functions

g

or

h

and the parameters

po,q,

or

a,,b,

are suitably chosen (see Section 11). A graphical

picture

of

these representations is given in Fig.

1.

Ideally,

one would like these representations to be reasonably

“sharp.” If e.g., the pair

(mo,

no)

corresponds to the time

t,

and the frequency

w,

(see Fig.

11,

then we would wish

that the frequency content, in a band around

wo,

of the

signal

f,

during a time interval around

to,

is essentially

mirrored by the coefficients

(g,,,f)

or

(h,,,f)

with

m

close to

mo,

n

close to

no.

It is intuitively clear that the

basic analyzing functions

g

or

h

have to be themselves

well localized in time and frequency for such “sharpness”

of the associated representations to be attainable.

In this section we shall try to make these qualitative

statements more precise. We shall do this by giving a

sense to the “sharpness”

of

the time-frequency represen-

tation, and by showing how the localization, in time and

frequency,

of

the analyzing functions

g

or

h

matters. The

Weyl-Heisenberg case shall be discussed in Section 111-A,

the wavelet case in Section 111-B. In both cases we shall

see that signals that are essentially limited to a given

finite time interval and to a given finite range in fre-

quency can essentially be represented by a finite number

of expansion coefficients. (All these qualifications will be

made more quantitative next). We shall use this fact to

explain, in Section 111-C, a phenomenon that was first

noticed by

J.

Morlet in numerical calculations. To recon-

struct

a

signal

f

with a precision

E,

it is sufficient, for

some frames,

to

calculate the expansion coefficients with

a precision

CE,

where

C

turns out to be significantly

larger than would be expected for orthonormal bases. We

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL. ANALYSIS

993

have called this phenomenon the “reduction of calcula-

tional noise” (for example, it often reduces round-off

errors), and we explain it in Section

111-C.

A.

The

Weyl-

Heisenberg Case

Assume that

g

is normalized,

/’&

Ig(x)12

=

1, and that

l~xlg(x)12=o=ldYYlg^(Y)12.

Then

g,,

is localized around the phase space point

hp,,nq,),

/&xlg,,(x)

I2

=

nq,,

/dyy((g,,)^

(Y)

l2

=

mp,.

Suppose, on the other hand, that we restrict ourselves

to the analysis and reconstruction of signals that are

essentially time-limited to the interval

[

-

T, TI

and essen-

tially band-limited (limited in frequency) to the interval

[

-

R,

RI.

We have introduced the word “essentially” in

this statement because, as is well-known, no function

f

can have both a compact support and a Fourier transform

with compact support. A more precise statement of the

“essential” time- and band-limitedness is

11(1-

QT>fII

<<

llfll

11(1-

Pn)fll

<<

llfll

(

QT~)

(1)

=

X[

-

~,~I(t)f(t)

where

VnfY

(w)

=

X[-n,n](w)f(w)

and where

x,

denotes the indicator function of the inter-

val

I.

Effectively, these limitations single out a rectangle

of phase space as more important than other regions.

We shall assume, in what follows, that the

g,,

consti-

tute a frame, with frame bounds

A

and

B

and with dual

frame

g,,.

The reconstruction formula, valid for all func-

tions in

L2(R),

and therefore in particular for the func-

tions

f

of interest here, is (see Section 11-A)

f=

C

irnn(grnn,f).

(3.1)

m,n

E

Z

If the

g,,

are “well localized” in phase space around

(mp,,nq,),

then it is to be expected that

(g,,,f)

will be

small if the distance, in phase space, from

(mp,,nq,)

to

the rectangle

[

-

R,

R]

x

[

-

T,

TI,

is large. In other words,

one expects that only those

m,

n

for which

(mpo,

nq,)

lies

in or close to

[

-

R,R]X[-

T,T]

will play a significant

role in the reconstruction (3.1)

of

f.

Fig.

6

represents the

situation.

As

in Fig. l(a), the

g,,

are represented by their

“phase space centers”

(mp,,

nq,).

The signal

f

is essentially concentrated, in phase space,

on the rectangle

[

-

R,

RI

X

[

-

T, TI.

Under suitable con-

ditions on

g,

it turns out that, for all

E

>

0,

there exist

t,,

w,

such that the partial reconstruction

of

f

using only

the (finitely many)

m,n

associated to the “enlarged rect-

angle”

[-(a

+

w,),(R

+

w,)lx[-(T

+

t,),(T

+

t,)l

(in

.

-

.

-k

I.

1.

I

t”

.

-c

.

+

t

*i

:

....

L-*-Z-*-Z--Z-*-Z-*-3

a.....

.

1

. . . . . .

Fig.

6.

Rectangular lattice

(nqo, mp,)

indicating localization

of

gmnr

and rectangle in phase space

[

-

T,

TI

X

[

-

0,

a]

on which signal

f

is

mainly concentrated. Coefficients

(g,,,

f)

corresponding

to

(nq,,

mpo)

in enlarged rectangle (in dashed lines) suffice to recon-

struct

f

up to error

of

order

E.

dashed lines in the figure), is equal to

f,

up to an error

of

order

E.

This is essentially the content

of

the following

theorem.

Theorem

3.1:

Suppose that the

g,,(x>

=

eimPoxg(x

-

nq,)

constitute a frame, with frame bounds

A,

B.

Assume

that

I

g(

x)

1

I

C(

1

+

x2)

-a,

1

g(

y)

1

I

c(1+

y2>-

for some

C

<w,

a

>

1/2. Then, for any

E

>

0,

there exist

t,,

w,

>

0

such that, for all

f

E

L2(R),

and for all

T,

R

>

0,

+

\I(

1

-

QT)fI(

+

ellfll]

(3.2)

Proof

See Appendix

D.

0

where the

g,,

constitute the dual frame to the

g,,.

Remarks:

1)

In the limit as

E

+

0,

one finds

t,

+w

or

w,

+W.

(With our proof, in Appendix

D,

both

t,

and

w,

tend to

03

as

E

+

0.

If

g

or

g

has compact support,

then

t,

or

w,

can be kept finite. In all cases at least

one

of

t,,

w,

must diverge as

E

+

0.)

This is natural;

infinite precision cannot be obtained when using

only a finite set of

g,,.

In particular, for

g(x)=

~-‘/~exp(- x2/2),onefinds

w,,t,

-E+OCllog~l’’2.

2) Note that the decay conditions on

g

and

2

exclude

all orthonormal bases

g,,,

by Theorem 2.3.

3) The important fact about Theorem 3.1 is that

c,,w,

are

independent

of

T,

R:

the “enlargement proce-

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

994

IEEE TRANSACTIONS ON INFORMATION THEORY,

VOL.

36,

NO.

5, SEPTEMBER 1990

dure” depends only on

E,

the desired precision of

the finite construction. For fixed

E,

the number of

points

N,(T,R)

used in this finite reconstruction is

4(T

+

t,XR

+

w,)/p,.q,.

Hence

lim (4TR)-’N,(T,R)

=(po.qo)-’,

(3.3)

T,R

--lm

which is independent of

E.

This can be compared

with an analogous result involving prolate spheroidal

wave functions (see [65], [66]; the formula discussed

here is explained very clearly in [66]). The prolate

spheroidal wave functions are the eigenfunctions of

the compact operator

PnQTPn

(which also de-

scribes localization in phase space, singling out the

rectangle

[

-

R,

RI

X

[

-

T, TI). Signals

f

that are

essentially time-limited to

[

-

T, TI and bandlimited

to

[

-

R,

R]

can be expanded in prolate spheroidal

wave functions. Again, if a reconstruction up to a

finite error

E

is

desired, one can truncate the expan-

sion to a finite sum. The number,

rt,(T,

R),

of

terms

needed is the number of eigenfunctions of

PnQ,Pn

with eigenvalue larger than

E.

One has [651, [661,

2TR

n,(T,R)

=

-

+

CElog(TR)

+

o(E).

7r

In this case

This limit is exactly the Nyquist density. In fact, this

result was the first rigorous formulation of the intuitive

Nyquist density idea [65]. If we compare (3.3) with (3.41,

then we see that in our present approach, the density

(po.qq)-l

is higher than the Nyquist density (2.srI-l. We

know indeed (see Section 11-C-la)) that

po.qo

_<

27r for

all frames

{g,,;

m,n

E

h}.

For the examples with good

phase space localization (measured by e.g., higher mo-

ments of

Jgl

and

lgl),

we even have, by Theorem 2.3, that

po*qo

<

27r.

The “oversampling” of our phase space den-

sity with respect to the optimal Nyquist density, measured

by the ratio 27r(pO.qJ1

>

1, is the price we have to pay

for the fact that the frames of interest to us

are, in

general, not orthonormal. We also gain something with

respect to the prolate spheroidal wave functions, however.

The construction of the different

g,,,

obtained from one

function

g

by translations in phase space, is simpler than

the Construction of the (orthonormal) prolate spheroidal

wave functions.

Note that (3.3) can in fact be considered as a definition

of the phase space density for the frame under considera-

tion. While we have used the term “phase space density”

before in heuristic discussions, (3.3) is the first mathemat-

ically precise statement justifying this terminology.

Example: In the Table

VI11

we give the values of

f,

=

w,

corresponding to given

E

for

g(x)

=

7r-’l4

exp(

-

x2/2),

in the cases

p,=q,=~’/~

and po=q,,=(7r/2)1/2. In

each case we have used (D.6) in the estimates.

TABLE

VI11

THE

“ENLARGEMENT

PARAMETER”

I,*

pII

=

ql,

=

1.25

E

t,

=

w,

0.1

0.05

0.01

2.52

2.78

3.31

0.005 3.51

0.001 3.94

0.0005 4.11

0.0001 4.48

p,l=90=~=1.77

E

1.

=

w,

0.1 2.55

0.05

2.81

0.01 3.33

0.005 3.54

0.001 3.97

0.0005 4.14

0.0001 4.50

*As

function

of

the error

E,

for

the

Weyl-Heisenberg frame

of

Gaussians,

respectively

for

po

=

90

=

m,

po

=

9”

=

J;;

(see text)

B.

The Wavelet Case

In this case we assume that

h

is normalized

so

that

jdr lh(x)I2

=

1,

and that

j’dxxlhJx)12

=

0.

Let us assupe,

for the sake of simplicity, that

Jhl

is even (in practice,

h

is

either even or odd; even if the frame

is

constructed by

means of a function

h

with support

h

c

R,,

then the

effective basic wnavelets

h’

=

Re

h, h2

=

Im

h

satisfy the

condition that

Ih’l

is even-see the remarks following

Theorem

2.7

and 2.8). Let us also assume that

(this does not imply any

loss

of generality: it can easily be

achieved by dilating

h).

Then

h,,

is concentrated around

the phase space points

(

t-

a;,,

arnb,)

Lrndkkl(

h,,)”

(k)

l2

=

akm

=

-

Io

dkkl(

hm,j

(k)

1’.

-m

Again, we suppose we are mainly interested in func-

tions

f

localized in phase space. In this case, we assume

that they are essentially time-limited to

[

-

T,

TI, and with

frequencies

IwI

mainly concentrated in

[a,,

a,], where

0

<

R,

<

R,

<

w.

The need for a lower bound

a,

on the

frequencies

Iw

I,

as opposed to the Weyl-Heisenberg case,

where we only introduced an upper bound, stems from

the logarithmic rather than linear treatment of frequen-

cies by

the

wavelet transform.

Fig.

7

represents the situation graphically. The dots

represent the “phase space localization centers” of the

hm,;

for the sake of simplicity we have taken

a,,

=

2. The

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES:

THE

WAVELET

TRANSFORM,

TIME-FREQUENCY

LOCALIZATION

AND

SIGNAL ANALYSIS

995

7

................................................

I

r-----T-----

I

+t

I

L-----

-----I

I

................................................

t

Fig.

7.

Lattice

Moa;,

k

aGrnk,),

indicating localization of

h,,

(see

Fig.

l(b)),

and

two

rectangles

[-T,T]X[R,,R,], [-T,T]x[-R,,

-

R,]

on

which signal

f

is mainly concentrated. Coefficients

(h,,,f)

corresponding

to

lattice points within set

B,

(in dashed lines) suffice

to

reconstruct

f

up to error

E.

signals

f

of interest are essentially concentrated in the set

[-

T,TlX([(-

RI,

-

R,]U[R,,R,]), marked with full

lines in the figure.

We shall assume, of course, that the

h,,

constitute a

frame, with frame bounds

A,

B

and with dual frame

(h,,J.

The associated reconstruction formula is then

This formula is valid for all functions in

L2(R).

For signals

essentially concentrated in

[

-

T, TI

X

([

-

RI,

-

R,]

U

[a,,

RI]) we can again restrict ourselves to a finite subset

B,(T,R,,R,)

of indexes, provided the basic wavelet

h

is

itself sufficiently concentrated. Partial reconstruction of

such a signal

f,

using only the pairs

(m,

n)

E

B,,

is then

an approximation of

f

with an error at most equal to

E.

The set

B,

includes all the

(m,n)

for which

R,

I

aim

I

RI,

and

Ja,“nb,l

I

T; it is indicated in dashed lines in Fig.

7.

The following theorem gives an exact statement of this

result.

Theorem

3.2:

Suppose that the

hmn(

X)

=

airnI2h(

aimx

-

nb,)

constitute a frame, with frame bounds

A,B,

and dual

frame

(h,,)“.

Assume that

where

p

>

0,

a

>

1, and that, for some

y

>

1/2

/&(

1

+

x2)’1

h(

x)

1’

<w.

Fix T

>

0, 0

<

R,,

<

RI.

Then, for any

E

>

0,

there exists a

finite subset

B,(T,R,,R,)

of

Z2

such that, for all

f

E

L2(R),

(3.6)

Proof

See Appendix D.

0

Remarks:

1) The “enlargement procedure,” i.e., the transition

from the original “box”

[-

T,TIx([-

RI,

-

R,]u

[R,,R,])

to B,(T,R,,R,), is more complicated here

than in the Weyl-Heisenberg case; the parameters

m,, m,,

and

t

also depend on

R,,R,

and not only

on

E

(see the proof in Appendix D).

2) The construction of the set

B,

(see also Fig. 7)

exhibits the fact that wavelets give a higher resolu-

tion at high frequencies than at low frequencies. For

fixed

m,

the “extension” of the box in the time-vari-

able, as defined by (D.7), corresponds to considera-

tion of all the pairs

(m,

n)

with time-localization

la,”nb,l

I

T

+

art.

The “extension”

art

thus de-

pends on

m

and is small for large negative values of

m,

which correspond to high frequencies.

3) A crude estimate leads to

#Be(

T,

a,

9

1

)

If

R,

+

0,

T, and

RI

+CO,

then

CE-

I/P

2bo In

a,

(4TR,)-’[#B,(T,R,,Rl)]

f

~

(3.8)

which is not independent of E. While the estimate

(3.7) is admittedly crude, finer estimates lead to a

similar result. This is in contrast with the analogous

result for the Weyl-Heisenberg case (see (3.3))

where the corresponding limit was independent of

E,

and gave the phase space density of the frame.

In

fact, it gave a procedure to

define

the phase space

density of the frame. Because

of

the €-dependence

of the right-hand side of (3.7), we cannot use the

same procedure to define a phase space density

corresponding to wavelet frames. This

illustrates

again (see also the discussion in Section II-C-2a))

that the concept “phase space density” is not well-

suited to the wavelet representation.

4) The estimates made in the proof

of

Theorem 3.2

lead to rather crude bounds. As in the Weyl-Hei-

senberg case, it is possible to write more compli-

cated, but less coarse estimates. For the choice

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

996

IEEE

TRANSACXONS ON

INFORMATION

THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

h(x)

=

2.3-1’2~-’/4(1

-

x2)e-x2/2,

a,

=

2.0,

b,

=

0.5,

with

fl,

=

10,

fl,

=

1000,

and

T

=

100,

one finds

E

mil

ml

t

0.1

-

11

-2

4.95

0.05

-

12

-2 4.97

0.01

-

13

-2 5.75.

C.

The

Reduction

of

Calculational

Noise

J.

Morlet noticed, some time ago, that in numerical

wavelet calculations, it often sufficed to calculate the

wavelet coefficients to a precision of, say, to be able

to reconstruct the original signal with a precision of, say,

This rather surprising fact can be explained as a

consequence of both phase space localization, and “over-

sampling.”

Phase space localization is necessary to restrict oneself

to a finite number

of

coefficients. We cannot hope to

control an infinite number of coefficients if they can all

induce an error of the same order. The role

of

“oversam-

pling” is the following. Let us go back to the frame

operator

T

(not to be confused with the time-limit

T

in

Sections 111-A and 111-B) defined in Sections I-C and

11-A. We have

T:

L2(R)

+

12(E2)

(Tf)m,n

=

(4rnn9f)

where

+,,,

stands for either

h,,

or

g,,.

Since the

4m,

constitute a frame, this operator is bounded and has a

bounded inverse on its closed range. The operator

T

is

onto (its range is all of

12(Z2))

if and only

if

the

$,,,

constitute a basis. In general, however, the

4,,,

are not

independent, and the range

of

T (RanT)

is a proper

subspace

of

12(Z

2).

The inversion procedure,

f=

C

(4rnn)-(4rnn?f)

m,n

when applied to elements

c

of

12(Z2)

not necessarily in

Ran

T:

C

(4mn)“Cmn

m,n

in fact consists

of

1)

a projection of

12(Z2)

onto

RanT,

2)

the inversion of

T

on its range (see Section 11-A). We

shall model the finite precision

of

numerical calculations

by adding random “noise” to the coefficients

(4,,,

f),

thus leading to modified coefficients

c,,,(f).

The “noise”

component of these coefficients “lives” on all of

12(Z2).

If

we apply the inversion procedure, this component will

therefore be reduced in norm by the projection onto

RanT.

This reduction will be the more pronounced the

“smaller”

RanT

is, as a subspace

of

12(Z2),

i.e., the more

pronounced the oversampling of redundancy in the frame.

The calculations below show how this work in practice.

Let us assume that we are interested in signals

f

that

are essentially localised in the time interval

[

-

T, TI,

and

in the frequency range

[

-

R,

fl]

(in the Weyl-Heisenberg

case) or

[-

RI,

-

fl,,]U[fl,,,fl,]

(in the wavelet case), i.e.,

I\(

1

-

Q~)fl(

I

~llfll

II(

n

-

~,)fll

I

~Ilfll

or

II(

n

-

pn,

+

p,,,)fI(

I

EII~II.

Then, by Theorems

3.1

and

3.2,

there exists an “enlarged

box”

B,

such that

llf-

c

(4rno)-<+rnn,f>

11

5

3(~/~)1/~Ellfll

(m,n)E

E,

where

4

denotes either

g

or

h.

Since

B,

is a finite subset

of

E’,

we restrict ourselves therefore to the finitely many

coefficients

(+,,,

f).

In practical calculations, the coefficients

(4,,,

f

)

will

be computed with finite precision. Let us take the follow-

ing model for the errors. Assume that the coefficients to

be used in the calculations are given by

cmn(f)

=

(4mn,f)

+

ymn

where the

ymn

are independent identically distributed

random variables, with mean zero, and with variance

a2,

E(y&J

=

a’.

This means that the

(4,,,f)

are known with “precision”

a.

Note that our model is only a first approximation. In

general the

$I,,,,

and hence the

(+,,,f),

are not linearly

independent, which means that the round-off errors

should not be regarded as independent random variables.

With this approximation, we find that the estimated error

between

f

and a partial reconstruction, using only the

finitely many coefficients associated to

(m,

n)

E

B,,

and

even those only with finite precision (i.e., replace

(4,,,

f

)

by

c,,,(fN,

is

given by

=

#-

(,,,)E

c

E,

(4rnn)-(4rnn,f))

-

c

ymn(

4rnn)-

(m,n)EB,

I

9( B/A)~~llfIl~

+

A-2a2N,

(3.9)

where

N,

=

#Be,

and where we have used

E(y,,)

=

0,

E(-yrnnym.,.)

=

t3mm,8nnfa2,

and

Il(4,,)-

112

=

~~~-14mn~~2

I

A-2114mn112

=

A-2

(with

U

as defined in Section 11-A).

The “reduction of calculational noise,” observed by

J.

Morlet, is contained in the second term in

(3.91,

more

particular in the factor

N,A-*.

Let us show how.

Assume that we are considering a snug Weyl-Heisen-

berg frame,

gm,.

If we assume that

B,

is large with

respect to the lattice mesh, then (see Section 111-A)

4Tfl

Po

‘

9,

N,

=

#B,

-.

On the other hand,

if

the frame is snug (i.e.,

B

=

A),

we

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM. TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

997

find, by (2.2.9),

A-27r(p0.q,)-’

(we assume

llgll=

1). Hence

N,A-Z=

7r-2TR(po.q0).

(3.10)

If the

g,,

had constituted an orthonormal basis, then

(provided we neglect the

loss

in phase space localisation

due to the use of an orthonormal basis) this factor would

have been

(NcA-2)orthon.basis

(T).

(3.11)

The frame gives thus

a net gain

of

27r/po.q0 with

respect to the orthonormal basis situation.

Something similar happens for wavelets. In this case we

don’t have such a simple expression for

NE,

but we can

easily see that the same phenomenon takes place by the

following argument. Suppose

h,

U,,

b, are chosen

so

that

the frame is snug (i.e., it is tight for all practical purposes).

In particular this means that

m(h;

a,)

=

M(h;

U,)

while

the p-terms in (2.3.231, (2.3.24) are negligible. Conse-

quently

A

=

B

2:

27rb;’m(h;

U,).

Consider now the frame

with the same

h,u,,

but with bh

=

b,/2. This frame will

obviously also be snug, with

A’

=

B‘

2:

27rbh-’m(h;

a,)

=

2A. On the other hand, there are twice as many points in

the graphical representation of this new frame, for every

frequency level. Hence

N,‘

=

2Nf. Combining these two,

we find

N,‘AfW2

=

iN,A-2,

i.e., halving

b,

leads to a gain

of 2 in the total error

on

f,

for the same precision

on

the

coefficients.

For the frames used by

J.

Morlet when he noticed this

phenomenon, which were heavily oversampled (e.g., he

used up to

15

“voices”-see the end of Section 11-C-2a

for a definition), a gain factor of

10

or more can be

obtained easily. Note, however, that oversampling does

not explain completely the observed calculational noise

(or quantization noise) reduction.

As

in vision analysis

[38] part of the reduction is a consequence of the fact

that, unlike the original signal, the coefficients

cm,(f>

at

every fixed m-level are distributed around zero, with a

sharp peak at zero. This makes it possible to drastically

reduce the number

of

quantization steps in the

cmn,

without significantly altering the quality of the recon-

structed signal [381.

2TR

IV. CONCLUSION

We have shown how to characterize functions

f

by

means of a local time-frequency analysis, by computing

their inner products with either Weyl-Heisenberg coher-

ent states,

or with wavelets,

c,,(

f)

=

~,~/’/dXf(

x)h(

ugmx

-

nb,,)

The first approach corresponds to the windowed Fourier

transform, the second is the wavelet transform. The

wavelet transform handles frequencies in a logarithmic

rather than linear way, and seems better adapted to the

analysis of acoustic and visual signals than the windowed

Fourier transform.

In both cases we have formulated necessary and suffi-

cient conditions for the stable reconstruction

of

f

from

the

c,,<f).

For such a stable reconstruction algorithm to

exist, we require that, for some

A

>

0,

B

<m,

and all

Allfll’

I

Ic,,(f)

1’

I

Bllfl12.

(4.1)

We have provided a reconstruction algorithm, which con-

verges at least as fast as a geometric series in

r

=

B/A

-

1,

and we have presented efficient methods for estimating

A

and

B.

These methods are illustrated by many exam-

ples.

Finally, if

g

respectively,

h

is well localized in both

time and frequency, and

if

(4.1) is satisfied, we have

shown that the characterization of functions

f

by their

coefficients

cm,(f)

is truly local in time-frequency. If

f

is

essentially concentrated

on

a limited region in time-

frequency, then only the

cm,(f)

corresponding to time-

frequency points within or close to this region are needed

for an approximate reconstruction of

f.

f

E

L2(W

m,neZ

ACKNOWLEDGMENT

It is a pleasure for me to thank the many people with

whom

I

have had enjoyable discussions

on

the subject of

this paper, who pointed out relevant references, and who

raised interesting questions. First of all, I want to express

my gratitude to

A.

Grossmann, who introduced me to the

many properties of coherent states years ago, and more

recently stimulated my interest in “frame problems.” This

paper would not have existed without his continued inter-

est and encouragement. It has been a pleasure to discuss

the topics in this paper with him.

The completed proof of the Balian theorem, in Section

11-C-la), is due to

R.

Coifman and

S.

Semmes. I want to

thank them for letting me include it here. Thanks are also

due to

R.

Howe and

T.

Steger for solving one of my

conjectures and for drawing my attention to reference

[49]. The refinements of the frame bounds in Section

11-C-2a) are due to Ph. Tchamitchian. Section 11-D,

on

frame bounds and convergence in other spaces than

L2(R),

would not have existed without

Y.

Meyer and Ph.

Tchamitchian, who pointed out the problem to me, and

who suggested that a modification of the L2-estimates

would lead to useful Sobolev-space estimates.

I

would also like to thank P. Deift, H. Feichtinger, P.

Jones,

H.

Landau, P. Lax,

R.

Littlejohn, M. Sirugue, and

D. Thomson for many interesting discussions on one or

several subjects of this paper.

I

am also grateful to

C.

Tomei and to J.

R.

Klauder, who suggested the terminol-

ogy

“tight frame” and “snug frame,” respectively.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

998

IEEE

TRANSACTIONS

ON INFORMATION THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

Finally,

I

would like to thank the referees for making

many

suggestions that improved the readability of this

paper.

APPENDIX A

RESOLUTIONS

OF

THE

IDENTITY

By explicit computation we have

1

da

=

-

/

/db

/dyfi(

x

)

*

I

a

I

fi

(a)

fi

(

ay)

-y’f2(

y

)

2T

a

APPENDIX

B

PROOF

OF

LEMMA

2.4

We assume that

IG(t,

s)

I

b

<m

(B.1)

and that

G,

d,G

and

a,G

are locally square integrable. We show

that, together with the “periodicity conditions”

G(t

+l,s)

=G(t,s)

G(t,

s

+

1)

=

e2Ti‘G(

t,

s)

(B.2)

the extra assumption

JG(t,s)l?a>O

(B.3)

necessarily leads to a contradiction. To do this we introduce an

averaged version

Gr

of

G.

More precisely, define, for r

>

0,

Then

G,

is obviously continuous. For

It

-

t’l

<

r,

Is

-

s’I

<

r one

has

I

Gr(

t

,

s)

-

Gr(

t’,

s’)

I

br-

(

It

-

t’/

+

IS

-

s’l)

.

(B.4)

(B.21, but instead a modified version of them:

G,(t+l,s)=G,(t,s)

1

Gr

(

t

,

s

+

1

)

=

-

/

dt’

i

eZT“’G(

t’,

s’)

4r2

1t’-

11

<

r

s’-

SI

<

r

=

e

TirGr

(

t

,

s

)

+

(

t

,

s

)

03.5)

I+(~,s)II

2rbr. (B.6)

where

By choosing r small enough, we can make the deviation of (B.5)

from (B.2), as small as desired. The only other ingredient

needed

is

a set of bounds (upper and lower) on

lGrl.

The upper

bound is immediate from (B.l),

IG,(t,s)li

b.

For the lower bound we restrict ourselves to a neighborhood

U

of

[0,

212. Choose r such that, for all

(t,

s)

E

U,

The function

Gr

does not satisfy the “periodicity” conditions

,

,\

I

/I

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

999

If we choose

a

=

a/8b,

E

=

aa/8

=

a2/64b,

then the right

hand side of

(B.10)

reduces to

a/2,

and we conclude

a/21IG,(t,s)ls b. (B.ll)

We have now all the necessary ingredients. Since

G,

is contin-

uous, and satisfies

(B.11)

on

U,

with

a

>

0,

b

<m,

y,

=

log

G,

can

be defined as a continuous, univalued function on

U.

As

a

consequence of

(B.5)

we see that, for all

(t,s)~

V=

U

n

(U

-(l,O))n(U

-(O,

l)),

yr(

t

+

1,

s)

=

y,(

t

,

s

)

+

2aik

y,(

t,

s

+

1)

=

yr(

t,

s)

+

2ail+ 2ait

+

+(

t

,

s)

(B .12)

where

k,l

are integers, constant over all of

V,

because of the

continuity of

yr,

and where

I$(t,s)l

-

<

2-

IC,(

2,

s

I

provided

I+(?,

s)

I

IG,(t,

s)1/2.

For this

it

is sufficient (see

(B.6))

to impose r

I

a/(4rb),

which we can do without loss of the

previous estimates. One finds then

14(t,s)[Il,

forall(t,s)EV.

By

construction

V

is a neighborhood of

[0,1l2.

In particular

(B.12)

is valid on

[0,1]*,

which is enough to again lead to a

contradiction. We have

0

=

~r(

191)

-

Yr(1,O)

+

~r(1,O)

-

rr(O,O)

+Y,(O,O)-Y~(O,~)+Y,(O,~)-Y,(~,~)

=

2ail+ 2ai

+

4(

1,O)

+

2rik

-

2ail-

4(

0,O)

-

2aik

=2ai+4(1,0)-4(O,O)

#O

since

I

4(1>0)

13

I4(0,0)

Is

1.

This contradiction concludes the proof.

APPENDIX

C

PROOF

OF

THE

THEOREMS

IN

SECTION

111-B-3

Proof

of

Theorems

2.5,

2.6:

Using the Poisson formula

2a (x-;k)

I€Z

=

a

ktL

=

we find

0

integral over

x,

and once on the sum over k),

C

I(gmn,f>I*

m.n

The decay condition

(2.3.13)

on

P

implies that the sum over

k

always converges. It also implies that this sum tends to zero for

pO

+

0,

so

that the coefficient of

II

f

11'

in

(C.1)

is strictly positive

for small enough

po.

On the other hand, we also have

m,n

(C.2)

for all

po

>

0.

Together, the lower and upper bounds

(C.1)

and

(C.2)

imply that

P:

>

0,

with

Pi

=

inf

(

pol

the

g,,

associated to

g,

pO,

q0

do not constitute a frame).

This proves Theorem

2.5.

The inequalities

(C.l)

and

((2.2)

also

immediately prove Theorem

2.6.

0

The proofs of Theorems

2.7

and

2.8

are very similar.

Proofs of Theorems

2.7

and

2.8:

One uses the unitarity of

the Fourier transform to write

Hence, separating the sum over

k

into the term for

k

=

0

and a

sum over

k

#

0,

and applying Cauchy-Schwarz (once on the

As

in the proof of Theorem

2.5,

this can be rewritten with the

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

loo0

IEEE

TRANSACTIONS

ON

INFORMATION

THEORY,

VOL.

36,

NO.

5,

SEPTEMBER

1990

help of the Poisson formula,

into (C.51, and defining

m"= m

-

m',

one finds

The same arguments as in the proofs of Theorems

2.5

and 2.6

then lead

to

the desired conclusions.

0

Applying Cauchy-Schwarz twice, in the second term (once on

0

estimates

(2.3.25)

and

(2.3.26).

In

the

where

'

=lw+?

and

the

frame

Ih;n

Im,n

the sum over

m",

and Once on the integral Over

x)

leads to the

E

z)

is used (see Section

II-C-za)),

one has to be a little more

careful. The equivalent of (C.1) is then

b,

<

2.

In the computation of

PI,

it

is sufficient to take the supre-

mum over

x

E

[2ir/3, 4ir/3]. For

x

in this interval, and for

Proof of Theorem

2.10:

For

b,,

=

1,

the

$mn;l

are

Y.

Meyer's

basis. We start by showing that the

$m,n:bll

still constitute a

frame for

6,

in a neighborhood of

1.

For

b,

=

2, the

$mn;z

=

$m

2n:

do not span

L'(R).

We therefore restrict our attention to

with

Is1

2

2irb;'

2

ir, one finds that only the couples

(m, m')

E

{(

-

2,2),

(

-

1,1),(

-

1,2),

(O,O),(O,

11,

(1,O))

lead to nonzero con-

tributions to

P,.

As the supremum of the sum of a finite number

112

of continuous -functions,

-PI

is therefore continuous. On the

other hand, since support

$

c

[

-

8ir/3,8ir

/3],

one finds that

P,(s)=

0

if

Is1

2

16ir/3. For

b,

<

2, this implies that only the

choices

1

=

0,

1 or 2 lead to nonzero contributions in the sums

(2.3.251, (2.3.26). This implies that the right hand sides of

(2.3.251, (2.3.26) are continuous in

b(].

For

bo=

1 these two

expressions are equal to

1.

By continuity we find therefore that

(2.3.25)

>

0

and (2.3.26)

<

m

on a neighborhood of

b,

=

1.

I

r

I

fi

[

/6".

lfi(

U

rx

)

I

fi

(

arx

+

k

)

I

f

(

x

)

1'1

(

kfO

To

show that the

$mn;bll

constitute a basis, we introduce the

operator

S(bO)

=

$mn;bl,($mn;l~

'>.

+

[

kxdu

lk(

urx>

I

fi

(arx

+

2

k

)

1

I

f(

-

x)

1'1

'I2

m

m,n

In the terminology of Section 11-A, we can write

S(b")

=

T(bn)*T(l)

where T(b,,), T(1) are the frame operators for the frames

$mn;bll,

$mn;l

respectively.

To

prove that the

$mn;bll

constitute a

basis, it is sufficient to prove that

S(b,,)

is one-to-one and onto,

since

S(b,)$mn;l

=

$mn;bll.

Since T(1) is unitary, and T(bO)* is

S(b,)

is one-to-one. We have

This leads again to the same bounds (2.3.231, (2.3.24).

proof

of

Theorem

2.9:

Applying the Poisson formula gives

Onto (see Proposition

we

Only

need

to

prove

that

T(b(l)*

Or

Any

kEZ,

k#O

can be decomposed, in a unique way, as

k

=

2"'k',

where

m',

k'

E

Z,

m'

2

0

and

k'

odd. Substituting this

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS

1001

Since support

4

=[-8a/3, -2a/31~[2a/3,8a/3],

and

a,,

=

2,

($m,,;bl,,4)

=

0

for Iml

>

1.

One checks easily, using

I+(X)I<C,(l+/x12)-N

that

C

l(+mn;~,l~+)l

fl€Z

converges, and is continuous in

b,,

for m=0,

kl.

Hence the

coefficient

of

11

f

in the right-hand side of

(C.6)

is continuous

in

b,.

Since this coefficient is equal to

1

for

b,,

=

1,

it is

therefore strictly positive on a neighborhood of

b,,

=

1.

This

implies that, on that neighborhood,

S(b,,)

is one-to-one. This

concludes the proof.

0

APPENDIX

D

PROOFS

OF

THE

THEOREMS

IN

SECTION

111

Proof of Theorem

3.1:

Since the g,, constitute a frame,

with dual frame

imn,

we have, for all

fl,

f2

E

L2(R),

(f27fl>=

C

(f2,imnJl).

m.n

E

Z

Fix T,

a

>

0.

For

t,

o

>

0

we define

constitute frames, with frame constants

A,

E

and

I?-',

A-',

respectively. Similar to the proof of Theorem

2.5

we use the

Poisson formula to estimate the last two terms in

(D.1).

This

leads to

Inq,,lT

+

I

l€H

From the conditions on g, we have

(D.2)<:C2

SUP

[I+(x-nq,)2]-a

/"4,]1>

T

+

I

E

Z

1x1

5

7-

27r

lx

-

-/I

5

T

PI1

-a

[l+(x-nq,--~l)']

.

(D.3)

The contribution for

n

>

(T

+

t)/q,

is exactly equal to that for

n

<

-(T

+

t)/q,,

so

that we may restrict ourselves to negative

n,

at the price of a factor

2.

By redefining

y

=

x

-(2a/p0)1

if

1

is positive, we see that we may restrict ourselves

to

negative

1

as

well. Hence

(D.3)<4C2

sup

[l+(~+nq,)~]-~

"q">T+lI20

lxl5T

27r

lx

-

--I1

I

T

P

I1

-a

,

[

1

+

(nq,

-

T

+

However, for any

a,

b

>

0,

we have

[l+(a+bf)y

I20

5(1+

a2)-a

+

$iX(l+*2)-Q

<

1+22.-lb-'(l+-)](1+a') 1

-[

2a-1

-

a

+

1/2

9

where we have used the fact that the

g,,,

and the

i,,,

both

if

a

>

1/2.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

1002

IEEE

TRANSACTIONS ON

INFORMATION

THEORY, VOL.

36,

NO.

5,

SEPTEMBER

1990

Consequently

One then has (see the proof of Theorem

3.1)

P(2a

-

1)

-2a

+

1/2

-

<

sup

c

I

(

fl>

(h,,,,

1-

)

I

.

c

[1+(nqo-T)2]

nqo

>

T

+

I

llfll=

I

nEZ

m

<

ml,

or

m

>

ml

A

similar argument shows that, for

t

2

2qo,

nqo

>

T

+

f

-2a

+

1

2-"[l+(t-2q(1)2]

.

+

I

(hmn

(

1

-

pri,

+

pfi,)f)

I]

+

SUP

I<fl>(hmn)->l

llflll

=

1

mll

sin

s

ml

lnhlll

z

a(l'"T

+

I

We find therefore that there exists a constant

~(p~),q~)),

inde-

pendent

of

T

or

t,

such that

I

1

\

1/2

I

+

K(q0,Po)1/2(1+

~2)-'a+1/2]11fll},

(D.5)

since

(1

+

t2)-2a+1,

(1

+

w~)-'~+'

0

for

t,w

+

0,

this proves

+

B-

I/2

[

mII

s

m

s

ml

I(hmn9QTf);l)).

(D.8)

the theorem.

0

Inbol

z

ac'"T

+

I

Remark:

The estimates in this proof cause

t,,

U,,

when calcu-

lated using

(DS),

to be much larger for a given

E,

and e.g., for

Gaussian

g,

than observed in numerical calculations. The inter-

mediate estimate

(D.2)

leads to much better values of

t,

(a

One has

similar formula can of course be written for

Pflf,

leading to

estimates for

we).

If we define

>

ml

<

I(hmn,(~~i,-~~,l)f)12

nEZ

m

2P

-

<-

c

dY

5

*

(t

;

Y

=

SUP

c

I

dx

*

W")

I

g(x

-

Y

*

W")

I

then

~(p,,,

qo)1/2,

in the estimate

(DS),

can be replaced by

+x>r

n=O

6"

m

>

ml

orm

<

m,,L,is

lyl

s

a1

/Eh

277

bo

*(x

-

y)>

f

all

5

ly

-

a["'-/ls

a,

The same thing can be done for

K(qo,

po)'/2.

Proof

of

Theorem

3.2:

We define the set

B,

as

B,(T,R,,R,)

=

((m,n);

mo

I

m

I

ml, In6,,l

I

a;"'T+

t)

(D.7)

where

mo,

MI,

and

t,

to be defined next, depend on

no,

n,,

and

E.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

DAUBECHIES: THE

WAVELET TRANSFORM,

TIME-FREOUENCY

LOCALIZATION

AND

SIGNAL

ANALYSIS

1003

where we have used that, for all

x

E

R,

(1+

x’)[l+(x

-S)’]4(S)

2

1

with

4

defined by

If we choose

1

<

K

<

a,

then

l€Z

and

Using the same techniques as in the proof

of

Lemma

2.2,

one

finds, for

RI,

I

lyl,

[

a;”lfl,]-2‘*

-

K)

1

I----

In

a,

2(a

-

K)

where we have assumed that

m,

2

(In

P

-

In

(a

-

K)

-

In R,)/ln

a(,.

Similarly, for

lyl

I

RI,

provided

m,,

I

(In

p

-

In(a

-

K)-

In R,,)/ln

a,,.

It is clear from

this that, for

a,,,

RI,

E

given, we can choose

mu,

mI

so

that

(D.lO)

Since

y

>

1/2,

this converges. It is moreover clear that

t

can be

chosen

so

that the coefficient of

llf1I2

in (D.10) is smaller than

Be2/4(rn1

-

m,,

+

l), i.e., such that

l(hm,,QTf)l2

I

Be2/411f1I2.

(D.11)

m,lsmsml

b,,lnl>

armT

+

f

The statement

(3.6)

now

follows directly from (D.81, (D.9) and

(D.11).

U

REFERENCES

D. Gabor, “Theory of communication,”

J.

Inst. Elect. Eng.

(London),

vol.

93, no.

111,

pp. 429-457, 1946.

M. J. Bastiaans, “Gabor’s signal expansion and degrees

of

free-

dom of a signal,”

Proc. IEEE,

vol.

68, pp. 538-539, 1980.

-,

“A sampling theorem for the complex spectrogram and

Gabor’s expansion

of

a signal in Gaussian elementary signals,”

Optical Eng.,

vol.

20, pp. 594-598, 1981.

A.

J. E. M. Janssen, “Gabor representation of generalized func-

tions,”

J.

Math. Appl.,

vol. 80, pp. 377-394, 1981.

~,

“Gabor representation and Wigner distribution of signals,”

in

Proc. IEEE,

1984, pp. 41.B.2.1-41.B.2.4.

M.

J.

Davis and E.

J.

Heller,

J.

Chem.

Phys.,

vol.

71, pp. 3383-3395,

1979.

J.

R. Klauder and E. Sudarshan,

Fundamentals

of

Quantum Optics,

New York: Benjamin, 1968.

R.

J. Glauber, “The quantum theory of coherence,”

Phys. Rec.,

vol.

130, pp. 2529-2539, 1963; “Coherent and incoherent states of

the radiation field,”

Phys. Rev.,

vol.

131, pp. 2766-2788, 1963.

J.

R. Klauder and B.-S. Skagerstam, “Coherent states,” Singa-

pore: World Scientific, 1985.

E.

Lieb, “Thomas-Fermi theory and related theories of atoms and

molecules,”

Re[,. Mod. Phys.,

vol.

53, pp. 603-641, 1981.

G.

A. Hagedorn, “Semiclassical quantum mechanics

I:

The

ii

0

limit for coherent states,”

Comm. Math. Phys.,

vol.

71, pp. 77-93,

1980.

C.

W. Helstrom, “An expansion

of

a signal in Gaussian elemen-

tary signals,”

IEEE Trans.

Inform.

Theory,

vol.

12, pp. 81-82, 1966.

N.

G. de Bruijn, “Uncertainty principles in Fourier analysis,” in

Inequalities,

0.

Shisha, Ed. New York: Academic Press, pp.

T. A. C. M. Claassen and W. F.

G.

Mecklenbrauker. “The Wigner

distribution-A tool for time-frequency signal analysis,”

Philips

J.

Res.,

vol. 35, pp. 217-250, 276-300, 372-389, 1980.

C. P. Janse and A. J. M. Kaiser, “Time-frequency distributions of

loudspeakers: The application of the Wigner distribution,”

J.

Audio Eng. Soc.,

vol. 31, pp. 198-223, 1983.

R.

J.

Duffin and A. C. Schaeffer, “A class of nonharmonic Fourier

series,”

Trans. Am. Math. Soc.,

vol. 72, pp. 341-366, 1952.

57-71, 1967.

Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.

R. M. Young,

An Introduction to Nonharmonic Fourier Series.

New York: Academic Press, 1980.

1.

Daubechies, A. Grossmann, and

Y.

Meyer, “Painless non-

orthogonal expansions,”

J.

Math. Phys.,

vol. 27, pp. 1271-1283,

1986.

A. Grossmann and J. Morlet, “Decomposition of Hardy functions

ito square integrable wavelets of constant shape,”

SIAM

J.

Math.

Anal.,

vol. 15, pp. 723-736, 1984.

P. Goupillaud, A. Grossmann, and J. Morlet, “Cycle-octave and

related transforms

in

seismic signal analysis,”

Geoaploration,

vol.

23, p.

85,

1984.

A. Grossmann, J. Morlet, and T. Paul, “Transforms associated to

square integrable group representations,”

J.

Math. Phys.,

vol. 26,

pp. 2473-2479, 1985;

Ann. Inst. Henri Poincare‘,

vol. 45, 293-309,

1986.

E.

W. Aslaksen and J. R. Klauder, “Unitary representations of the

affine group,”

J.

Math. Phys.,

vol. 9, pp. 206-211, 1968; “Continu-

ous representation theory using the affine group,”

J.

Math. Phys.,

T. Paul, “Functions analytic on the half-plane as quantum me-

chanical states,”

J.

Math. Phys.,

vol. 25, pp. 3252-3263, 1984.

-,

“Affine coherent states and the radial Schrodinger equa-

tion.

I.

Radial harmonic oscillator and hydrogen atom,” to be

published.

C. Fefferman and

R.

de la Llave, “Relativistic stability of matter,”

Rep. Math. Iberoamericana,

vol. 2, pp. 119-213, 1986.

I.

Daubechies, “Time-frequency localization operators-A geo-

metric phase space approach,”

IEEE Trans. Inform. Theory,

vol.

34, pp. 605-612, 1988.

I.

Daubechies and

T.

Paul, “Time-frequency localization operators

-A geometric phase space approach

11.

The use of dilations,”

Ini,erse Problems,

vol. 4, pp. 661-680, 1988.

J. Morlet, G. Arens,

I.

Fourgeau, and D. Giard, “Wave propaga-

tion and sampling theory,”

Geophys.,

vol. 47, pp. 203-236, 1982;

“Sampling theory and wave propagation,” NATO AS1 Series, vol.

1,

Issues in Acoustic Signal /Image Processing and Recognition,

C. H. Chen, Ed. Berlin: Springer, pp. 233-261.

R. Kronland-Martinet, J. Morlet, and A. Grossmann, “Analysis of

sound patterns through wavelet transforms,” preprint CTP-87/p.

1981, Centre de Physique Thtorique, CNRS, Marseille, France,

1987.

A. Grossmann, “Wavelet transforms and edge detection,” to be

published

in

Stochastic Processes in Physics and Engineering,

Ph.

Blanchard, L. Streit, and M. Hasewinkel, Eds.

A. Grossmann, M. Holschneider, R. Kronland-Martinet, and J.

Morlet, “Detection of abrupt changes

in

sound signals with the

help of wavelet transforms,” in

Inrerse Problems: An Interdisci-

plinary Study, Adimces in Electronics and Electron Physics,

Supp.

19. New York: Academic, 1987.

S.

Mallat, “A theory for multiresolution signal decomposition,”

Ph.D. thesis, Univ. of Pennsylvania, Depts. of Elect. Eng. and

Comput. Sci., 1988.

A. Grossmann and J. Morlet, “Decomposition of functions into

wavelets of constant shape and related transforms,” in

Mathemat-

ics and Physics, Lectures

on